一棵树，结点树为n，根结点为r。每个结点都有一个权值ci，开始时间为0，每染色一个结点需要耗时1，
每个结点的染色代价为ci*ti（ti为当前的时间），
每个结点只有在父结点已经被染色的条件下才能被染色。
求染完整棵树需要花费的最小代价。
找出当前最大子节点和其父节点合并成新的节点
直到点集中只剩一个节点
因为合并时将子节点的权值加在父节点上
则 每次更新 答案加上当前子节点的权值乘上父节点的花费时间，这个很神奇
因为合并后，当对其父节点操作时也会重复加上子节点权值，
即累加起来等同于每一个节点的最初权值乘上对应时间
#include <iostream> #include <cstring> #include <cstdio> using namespace std; struct node{ int f,v,t; double w;//权值 }p[1005]; int n,r,a,b; int main() { while(~scanf("%d%d",&n,&r),n+r) { int ans=0; for(int i=1;i<=n;i++) { scanf("%d",&p[i].v); p[i].w=p[i].v; p[i].t=1; ans+=p[i].v; } for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); p[b].f=a; } double wmax; int pos,fa; for(int i=1;i<n;i++) { wmax=-1; for(int j=1;j<=n;j++)//找当前大子节点 { if(j==r) continue;//子节点！ if(wmax<p[j].w)//点权值比较时对比算数平均值 { wmax=p[j].w; pos=j; } } p[pos].w=-1;//去掉子节点 fa=p[pos].f; ans+=p[pos].v*p[fa].t;//更新答案 for(int j=1;j<=n;j++)//将子节点的子节点全部接在新建节点上 if(p[j].f==pos) p[j].f=fa; p[fa].v+=p[pos].v;//新节点在父节点位置，节点的总权值等同于父子权值和 p[fa].t+=p[pos].t;//个数 p[fa].w=1.0*p[fa].v/p[fa].t;//比较时权值等于算术平均值 } printf("%d ",ans); } }