这道题可以说是树形dp的入门题，也可以看成是一道检验【树】这个数据结构的题目；
这道题只能bfs，毕竟10^6的复杂度win下肯定爆栈了；
但是最恶心的还不是这个，实测用printf输出
用cout输出
题上也不提醒一下，无语啦；
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<string> 7 #include<iomanip> 8 #include<cmath> 9 using namespace std; 10 #define LL long long 11 const int maxn=1003000; 12 int n; 13 struct node{ 14 int y,next,v; 15 }e[maxn<<1]; 16 int linkk[maxn],len=0,siz[maxn],q[maxn],tail=0,fa[maxn],t[maxn],top=0,ru[maxn],w[maxn]; 17 LL ans=0; 18 void insert(int x,int y,int v){ 19 e[++len].y=y; 20 e[len].next=linkk[x]; 21 e[len].v=v; 22 linkk[x]=len; 23 } 24 void init(){ 25 scanf("%d",&n); 26 int x,y,v; 27 for(int i=1;i<n;i++){ 28 scanf("%d%d%d",&x,&y,&v); 29 insert(x,y,v);insert(y,x,v); 30 } 31 } 32 void bfs(){ 33 q[++tail]=1;int x; 34 for(int head=1;head<=tail;head++){ 35 x=q[head]; 36 for(int i=linkk[x];i;i=e[i].next){ 37 if(e[i].y==fa[x])continue; 38 q[++tail]=e[i].y; 39 fa[e[i].y]=x; 40 ru[x]++; 41 w[e[i].y]=e[i].v; 42 } 43 if(!ru[x])t[++top]=x; 44 } 45 for(int head=1;head<=top;head++){ 46 x=t[head];siz[x]++; 47 siz[fa[x]]+=siz[x]; 48 ru[fa[x]]--; 49 if(!ru[fa[x]])t[++top]=fa[x]; 50 ans+=(LL)abs(n-2*siz[x])*(LL)w[x]; 51 } 52 } 53 void work(){ 54 bfs(); 55 cout<<ans<<endl; 56 } 57 int main(){ 58 freopen("1.in","r",stdin); 59 freopen("1.out","w",stdout); 60 init(); 61 work(); 62 }