重心+BFS求调

#include <bits/stdc++.h>
#define int long long 
using namespace std;
constexpr int N=5e4+7;
int n,sum,h;
vector<int> e[N];
int d[N],m[N],p[N],a[N];
void fun(int v,int u){
	d[v]=1;m[v]=0;
	for(int i=0;i<e[v].size();i++){
		int x=e[v][i];
		if(x==u) continue;
		fun(x,v);
		d[v]=d[v]+d[x];
		m[v]=max(m[v],d[x]);
	}
	m[v]=max(m[v],n-d[v]);
	if(m[v]<m[h]||(m[v]==m[h]&&v<h)){
		h=v;
	}
}
void bfs(){
	queue<int> q;
	q.push(h);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<e[u].size();i++){
			int x=e[u][i];
			if(p[x]||x==h) continue;
			p[x]=p[u]+1;
			sum+=p[x]*a[e[u][i]];
			q.push(x);
		}
	}
}
int32_t main(){
	cin.tie(nullptr)->ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y,w;
		cin>>w>>x>>y;
		a[i]=w;
		if(x!=0){
			e[i].push_back(x);
			e[x].push_back(i);
		} 
		if(y!=0){
			e[i].push_back(y);	
			e[y].push_back(i);
		}
	}
	m[0]=0x3f3f3f3f3f3f3f3f;
	fun(1,0);
	p[h]=0;
	bfs();
	cout<<sum;
	return 0;
}