齐心抗疫

B. 齐心抗疫

树的直径有一个性质，即对于树上的每一个点，要找到一个最短路距离最远的点，结果一定是直径的两端点之一

所以遍历 n 个点，每次都假设当前点为a[]值较大点，然后找到一个距离最远的点，即直径的端点，最后贪心即可。

// Created by CAD on 2020/4/9.
#include <bits/stdc++.h>

#define mst(name, value) memset(name,value,sizeof(name))
#define ll long long
using namespace std;

const int maxn=5e4+5;
vector<int> g[maxn];
int a[maxn],dx[maxn],dy[maxn];
int dfs(int x,int f,int *d){
    int ans=x;
    for(auto i:g[x]){
        if(i==f) continue;
        d[i]=d[x]+1;
        int now=dfs(i,x,d);
        if(d[now]>d[ans]) ans=now;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n-1;++i){
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    int x=dfs(1,0,dx);
    mst(dx,0);
    int y=dfs(x,0,dx);
    dfs(y,0,dy);
    ll ans=0;
    for(int i=1;i<=n;++i)
        ans=max(ans,1ll*a[i]*max(dx[i],dy[i]));
    cout<<ans<<"\n";
    return 0;
}

齐心抗疫

原文：https://www.cnblogs.com/CADCADCAD/p/12672884.html