POJ 2054
题意 给你一棵树 然后给你根节点 其他节点染色的条件是父节点一定要被染色 我们知道如果父节点不需要被染色 那么很简单 贪心就好了 但是如果父亲节点需要染色 我们利用前面的性质 大点值一定是跟在父节点后面的 所以我们考虑 x y是一起的 那么 x y z
和z x y 分别是 x+2y+3z和 z+2x+3y 把他们都加上z-y再除以2 分别是 (x+y)/2 + 2z 和 z+(x+y)/2 * 2 也就是 x y 和 z等价为 (x+y)/2 和z的顺序 同理n数量的序列也可以这个样子取平均数作为他的排序标准 我们每次找最大的 和他的父亲合并 所以最后一次一定是根节点合成了所有点 其他的时候我们要用那个节点的父亲的数量 乘以 那个节点的点值 再让父亲合并子孙 合并以后父亲节点数目会更新 也就是模拟了我们的走的次数在增加 代码学习了lyd的风格
#include <cstdio> #include <cstring> #include <iostream> #include <stack> #include <queue> #include <map> #include <cmath> #include <set> #include <sstream> #include <algorithm> using namespace std; int n,r; const int MAX_N = 1025; struct node { int c,num,fa;double w; }arr[MAX_N]; int Find(){ double maxx = 0; int res; for(int i = 1;i<=n;++i) { if(i!=r&&arr[i].w>maxx) { res = i; maxx = arr[i].w; } } return res; } int main() { long long ans ; while(scanf("%d%d",&n,&r),n||r){ ans = 0; for(int i = 1;i<=n;++i) { scanf("%d",&arr[i].c); arr[i].w = arr[i].c; ans+=arr[i].w; arr[i].num = 1; } for(int i = 1;i<n;++i) { int a,b; scanf("%d%d",&a,&b); arr[b].fa = a; } for(int i = 1;i<n;++i) { int pos = Find(); int pa = arr[pos].fa; ans+=arr[pa].num*arr[pos].c; for(int j = 1;j<=n;++j) if(arr[j].fa==pos) arr[j].fa = pa; arr[pa].c += arr[pos].c; arr[pa].num += arr[pos].num; arr[pa].w = (double)1.0*arr[pa].c/arr[pa].num; arr[pos].w = 0; } printf("%lld\n",ans); } return 0; }
