解题思路
首先第一遍dfs预处理出每个点的子树的siz，然后可以处理出放在根节点的答案，然后递推可得其他答案，递推方程 sum[u]=sum[x]-(val[i]*siz[u])+(siz[1]-siz[u])*val[i]
代码
#include#include #include #include #include using namespace std;const int MAXN = 100005;typedef long long LL;inline int rd(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?x:-x;}LL ans,sum[MAXN],all[MAXN];int siz[MAXN],n,head[MAXN],cnt,to[MAXN<<1],nxt[MAXN<<1],val[MAXN<<1];inline void add(int bg,int ed,int w){ to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=w,head[bg]=cnt;}void dfs1(int x,int fa,int d){ all[x]=(LL)siz[x]*d; for(register int i=head[x];i;i=nxt[i]){ int u=to[i];if(u==fa) continue; dfs1(u,x,d+val[i]); siz[x]+=siz[u];all[x]+=all[u]; }}void dfs2(int x,int fa){ for(register int i=head[x];i;i=nxt[i]){ int u=to[i];if(u==fa) continue; sum[u]=sum[x]-((LL)siz[u]*val[i])+(LL)(siz[1]-siz[u])*val[i]; ans=min(ans,sum[u]); dfs2(u,x); }}int main(){ n=rd();int x,y,z; for(int i=1;i<=n;i++) siz[i]=rd(); for(int i=1;i