换根dp, father -> son , 基本是加减
#include <bits/stdc++.h> using namespace std ; const int N=1e5+2,M=N*5; #define int long long int n,a[N],sz[N],g[N],f[N],S; int nxt[M],go[M],w[M],hd[N],all; void add(int x,int y,int z){ go[++all]=y,nxt[all]=hd[x],w[all]=z; hd[x]=all; } void d0(int x,int fa){ int i,y,z; sz[x]=a[x]; for(i=hd[x];i;i=nxt[i]){ y=go[i],z=w[i]; if(y!=fa) d0(y,x),sz[x]+=sz[y]; } for(i=hd[x];i;i=nxt[i]){ y=go[i],z=w[i]; if(y!=fa) g[x]+=g[y]+sz[y]*z; } } void dfs(int x,int fa){ int i,y,z; for(i=hd[x];i;i=nxt[i]){ y=go[i],z=w[i]; if(y!=fa){ f[y]=f[x]-z*sz[y]+z*(S-sz[y]); dfs(y,x); } } } signed main(){ int i,x,y,z,t=1e9; cin>>n; for(i=1;i<=n;i++) cin>>a[i],S+=a[i]; for(i=1;i<n;i++) cin>>x>>y>>z,add(x,y,z),add(y,x,z); d0(1,0); dfs(1,0); for(i=1;i<=n;i++) t=min(t,f[i]); cout<<t+g[1]<<'\n'; }
标签:sz,Great,nxt,int,Gathering,fa,go,P2986,hd From: https://www.cnblogs.com/towboa/p/17278986.html