被傻逼题降智了。。
就是第一次dfs 时 求一次size，一次deep数组
然后第二次dfs时直接求最大值
先把结点1的值求出来，
u->v过程中，v子树的所有结点深度-1，v外的所有结点深度+1，这个过程等价于 u的值-size[v]+size[1]-size[v]
所以第二次dfs时把父亲的值传下去就好
/* 求一次size数组 求一次叠加的sum数组 每个点的权值就是sum[u]+u上面的权值 如何求u上面的权值 */ #include<bits/stdc++.h> #include<vector> using namespace std; #define maxn 200005 #define ll long long vector<ll>G[maxn]; ll n,a[maxn],size[maxn],sum[maxn]; void dfs1(int u,int pre){ size[u]=a[u]; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==pre)continue; dfs1(v,u); size[u]+=size[v]; } } ll d[maxn]; void dfs2(int u,int pre){ for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==pre)continue; d[v]=d[u]+1; dfs2(v,u); } } ll ans; void dfs3(int u,int pre,ll up){ ans=max(ans,up); for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==pre)continue; dfs3(v,u,up+size[1]-2*size[v]); } } int main(){ cin>>n; for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<n;i++){ ll u,v; scanf("%lld%lld",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs1(1,1); dfs2(1,1); for(int i=1;i<=n;i++) sum[1]+=d[i]*a[i]; dfs3(1,1,sum[1]); cout<<ans<<‘\n‘; }
原文：https://www.cnblogs.com/zsben991126/p/10913858.html