#4和#5没过

提交记录

#include<bits/stdc++.h>
using namespace std;
int n,cnt,u,v,d[100005],head[100005],dmax=INT_MAX,di;
long long int ans;
bool b[100005];
queue<pair<int,int> >q;
struct rumia{
	int people,next,to;
}t[100005];
void add(int u,int v){
	t[++cnt].to=v;
	t[cnt].next=head[u];
	head[u]=cnt;
	return;
}
void dfs(int x,int father){
	d[x]=1;
	int tmp=0;
	 for(int i=head[x];i;i=t[i].next){
	 	int k=t[i].to;
	 	if(k==father)continue;
	 	dfs(k,x);
	 	d[x]+=d[k];
	 	tmp=max(tmp,d[k]);
	 }
	 tmp=max(n-d[x],tmp);
	 if(dmax>tmp){
	 	dmax=tmp;
	 	di=x;
	 }
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&t[i].people,&u,&v);
		if(u){
			add(i,u);
			add(u,i);
		}
		if(v){
			add(i,v);
			add(v,i);
		}
	}
	dfs(1,0);
	q.push(make_pair(di,0));
	while(!q.empty()){
		int x1=q.front().first;
		int x2=q.front().second;
		ans+=x2*t[x1].people;
		b[x1]=true;
		q.pop();
		for(int i=head[x1];i;i=t[i].next){
			int k=t[i].to;
			if(b[k])continue;
			q.push(make_pair(k,x2+1));
			
		}
	}
	printf("%lld",ans);
	return 0;
} 

求大佬帮忙看看qwq