60分，用的树上DP的二次扫描与换根方法

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int INF=0x3f3f3f3f;
int head[N],tot=-1,n,l,r,w[N],dis[N],vis[N],dep[N],sz[N],dp[N],sum;
int ans,ma=INF;
queue<int> q;
struct nod{
    int ne,to,w;
}e[N*2];
void add(int u,int v,int w){
    e[++tot].ne=head[u];
    e[tot].to=v;
    e[tot].w=w;
    head[u]=tot;
}
void dfs1(int u,int fa){
    sz[u]=1;
    for(int i=head[u];i!=-1;i=e[i].ne){
        int v=e[i].to;
        if(v==fa)continue;
        dfs1(v,u);
        sz[u]+=sz[v];
    }
}
void dfs2(int u,int fa){
    for(int i=head[u];i!=-1;i=e[i].ne){
        int v=e[i].to;
        if(v==fa)continue;
        dp[v]=dp[u]+n-2*sz[v];
        dfs2(v,u);
    }
}
void bfs(int s){
	memset(dis,0x3f,sizeof dis);
	q.push(s);
	dis[s]=0,vis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=e[i].ne){
			int v=e[i].to;
			if(vis[v]==0){
				vis[v]=1,dis[v]=dis[u]+1;
				q.push(v);
			}
		}
	}
}
int main(){
    cin>>n;
    memset(head,-1,sizeof head);
    for(int i=1;i<=n;i++){
        cin>>w[i]>>l>>r;
        if(l!=0)add(i,l,1),add(l,i,1);
        if(r!=0)add(i,r,1),add(r,i,1);
    }
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=n;i++){
        if(dp[i]<ma){
            ma=dp[i];
            ans=i;
        }
    }
    //cout<<"_____________here______________";
    bfs(ans);
    for(int i=1;i<=n;i++)sum+=w[i]*dis[i];
    cout<<sum;
    return 0;
}