三倍的幸福！
暴力的做法就是枚举每一条边断开，选的两个点就是左右两棵树的重心。
可以发现找重心的时候一定是往权和大的子树找的，需要维护一个点的最大和次大子树，因为最大子树可能被割掉了，实际效率为O(NH)。
设sum[i]为子树i的权和，core[i]为i的子树中i作为重心的答案。
断掉一条边(x,y)的时候两棵树一棵包含根，一棵包含y，则一棵的答案为core[root]-core[y]-sum[y]*dep[y]，一棵为core[y]，找重心到x时更新答案now=now+sum[root]-2*sum[son]
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010; ll inf=1e18; struct poi{int too,pre;}e[maxn<<1]; ll n,m,x,y,z,tot,now,T; int last[maxn],fa[maxn],son[maxn][2],d[maxn]; ll sum[maxn],core[maxn],ans; void read(ll &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } void add(int x,int y){e[++tot].too=y;e[tot].pre=last[x];last[x]=tot;} void update(int x,int y) { if(!son[x][0]||sum[y]>sum[son[x][0]]) son[x][1]=son[x][0],son[x][0]=y; else if(!son[x][1]||sum[y]>sum[son[x][1]])son[x][1]=y; sum[x]+=sum[y];core[x]+=core[y]+sum[y]; } void ctr(ll &ans,int rt,int x,ll k) { ans=min(ans,k);int too=son[x][0]; if(too==now||sum[too]<sum[son[x][1]])too=son[x][1]; if(!too)return; ctr(ans,rt,too,k+sum[rt]-(sum[too]<<1)); } void dfs1(int x,int f) { d[x]=d[f]+1;fa[x]=f; for(int i=last[x];i;i=e[i].pre) if(e[i].too!=f) { dfs1(e[i].too,x); update(x,e[i].too); } } void dfs2(int x) { for(int i=last[x];i;i=e[i].pre) if(e[i].too!=fa[x]) { now=e[i].too;ll tree1=inf,tree2=inf; for(int k=x;k;k=fa[k])sum[k]-=sum[e[i].too]; ctr(tree1,1,1,core[1]-1ll*d[e[i].too]*sum[e[i].too]-core[e[i].too]); ctr(tree2,e[i].too,e[i].too,core[e[i].too]); for(int k=x;k;k=fa[k])sum[k]+=sum[e[i].too]; ans=min(ans,tree1+tree2);dfs2(e[i].too); } } int main() { ans=inf;read(n); for(int i=1;i<n;i++)read(x),read(y),add(x,y),add(y,x); for(int i=1;i<=n;i++)read(sum[i]); d[0]=-1;dfs1(1,0);dfs2(1); printf("%lld ",ans); return 0; }