Jennie

这也就是个裸的一批的换根dp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#define int long long
using namespace std;
int n;
int a[200005];
int x,y;
int head[200005];
struct e{
    int to;
    int ne;
}ed[400005];
int p;
int f[200005];
void add(int f,int to){
    ed[++p].to=to;
    ed[p].ne=head[f];
    head[f]=p;
}
int sum[200005];
void dfs(int no,int ff,int de){
    f[1]+=(de*a[no]);
    for(int i=head[no];i;i=ed[i].ne){
        int v=ed[i].to;
        if(v==ff) continue;
        dfs(ed[i].to,no,de+1);
        sum[no]+=sum[v];
    }
    sum[no]+=a[no];
}
void df(int no,int ff){
    for(int i=head[no];i;i=ed[i].ne){
        int v=ed[i].to;
        if(v==ff) continue;
        f[v]=f[no]+sum[1]-sum[v]-sum[v];
        df(v,no);
    }
    return ;
}
int ans;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<n;++i){
        scanf("%lld%lld",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,1,0);
//  cout<<f[1]<<endl;
    df(1,1);
    for(int i=1;i<=n;++i){
        ans=max(ans,f[i]);
    }
    cout<<ans;
    return 0;
}