学军网络邀请赛 - B 齐心抗疫（树的直径）

思路分析

简单说一下题意：任意选择两个点$u,v$，这两个点的贡献为$max(a_v,a_u)$$×dis(u,v)$，求最大值
该问题转化一下，就变成合理选择$u,v$,最大化$a_u×dis(u,v)$
先找出树的直径的两端，那么每一点，距离它最远的点一定是直径的两端
所以预处理出直径两端到各个点的距离就行了

样例输入

8
3 1 4 1 5 9 2 6
1 2
2 3
2 4
1 5
5 6
4 8
3 7

样例输出

45

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) x.size()
#define lowbit(x) x&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

vector<int>e[N];
int a[N],d1[N],d2[N];

int dfs(int u,int fa,int *dis) {
    int ans=u;
    for(auto v:e[u]) {
        if(v==fa) continue;
        dis[v]=dis[u]+1;
        int now=dfs(v,u,dis);
        if(dis[now]>dis[ans]) ans=now;
    }
    return ans;
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int x=dfs(1,1,d1);
    int y=dfs(x,x,d2);
    mem(d1,0);
    x=dfs(y,y,d1);
    int ans=0;
    for(int i=1; i<=n; i++) ans=max(ans,a[i]*max(d1[i],d2[i]));
    cout<<ans<<endl;




    return 0;
}