JZOJ5776. 【NOIP2008模拟】小x游世界树

题目：【NOIP2008模拟】小x游世界树；

题目的附加题解给的很清楚，这里只给一个代码；

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #define ms(a,x) memset(a,x,sizeof(a))

 #define ll long long

 using namespace std;

 const int MAXN=;

 struct node{

     int y,nxt;ll z;

 }edge[MAXN*];int indx=,n,head[MAXN];

 ll a[MAXN],ans=0x7fffffffff,rt=,siz[MAXN],f[MAXN];

 void add(int x,int y,ll z){

     edge[++indx].y=y;edge[indx].z=z;

     edge[indx].nxt=head[x];head[x]=indx;

 }

 void dp(int x,int fa){

     siz[x]=;

     for(int i=head[x],y;~i;i=edge[i].nxt){

         if((y=edge[i].y)==fa) continue;

         dp(y,x);f[x]+=1LL*edge[i].z*siz[y];

         siz[x]+=siz[y];f[x]+=f[y];

     } return ;

 }

 void dfs(int x,int fa,ll la,ll v){

     la-=v*siz[x];

     for(int i=head[x];~i;i=edge[i].nxt){

         if(edge[i].y!=fa) continue;

         la+=edge[i].z*(n-siz[x]);break;

     } if(la<ans) ans=la,rt=x;

     else if(la==ans) rt=min((int)x,(int)rt);

     for(int i=head[x],y;~i;i=edge[i].nxt){

         if((y=edge[i].y)==fa) continue;

         dfs(y,x,la,edge[i].z);

     } return ;

 }

 int main(){

 //    freopen("yggdrasil.in","r",stdin);

 //    freopen("yggdrasil.out","w",stdout);

     scanf("%d",&n);ms(head,-);

     for(int i=;i<=n;i++) scanf("%lld",&a[i]);

     for(int i=,x,y;i<n;i++){

         ll z;scanf("%d%d%lld",&x,&y,&z);

         add(x,y,a[x]>?z-a[x]:z);

         add(y,x,a[y]>?z-a[y]:z);

     } dp(,-);ans=min(ans,f[rt]);

     for(int i=head[];~i;i=edge[i].nxt)

     dfs(edge[i].y,,f[],edge[i].z);

     printf("%lld\n%lld\n",rt,ans);

     return ;

 }

树形DP与换根