color a tree poj2054

color a tree(贪心)

题目描述
可以得到一个确定性的结论，最大值的结点一定是在父节点染色后立即染色。
但是此时依结论不好在复杂的情况正推，先考虑简单情况：
假如有权值x,y,z三个点，已知x,y一定一起染色，则有两种可能方案：

1. 先x,y,再z，代价为X=x+2y+3z
2. 先z,再x,y，代价为Y=2x+3y+z
   X-Y=2z-x-y，当z>(x+y)/2时，X-Y>0，即先z再x,y的方案更优。

由此推广有两个数组
\(a_1+a_2+……+a_n\)
\(b_1+b_2+……+b_m\)
每个均为一个点，数组内依次染色，考虑何时显然第一组点：

• 先染\(a_i\),代价\(S_{ab}=\sum_{i=1}^n{a_i*i}+\sum_{i=n+1}^{n+m}{b_i*i}\);
• 先染\(b_i\),代价\(S_{ba}=\sum_{i=1}^m{b_i*i}+\sum_{i=m+1}^{n+m}{a_i*i}\);

则此时显然第一组点的条件为\(S_{ab}<S_{ba}\)，化简后得到\(\frac{\sum_1^n{a_i}}{n}\)<\(\frac{\sum_1^m{b_i}}{m}\)，即第一组点的平均值小于第二组点的平均值。

在考虑剩余点染色顺序时，将两组点分别看作两个点，其权值分别是两组点内所有点的平均值。
最终做法：每次找出当前权值最大的非根节点，将其染色顺序排在紧随父节点之后的位置，然后将该点合并进父节点中，更新父节点的权值。直到将所有点都合并进根节点为止。
如果直接按上述算法做的话，最终的分值不太容易计算，我们可以在将点合并的时候，实时更新当前的权值和：

• 最初所有点各自为一组，总分值是S=\(\sum_{i=1}^n{a_i}\)
• 接下来每次会将两组点合并，将其中一组点接在另一组点的后面。比如两组点分别是\(x_i\)和\(y_i\),将\(y_i\)接在\(x_i\)后面，\(y_i\)中每个点所乘系数都要增加偏移量为\(x_i\)中点的个数，假设为k,合并后，总的权值直接加上\(k*\sum{y_i}\)即可

代码如下：

// Problem: 给树染色
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/117/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=1010;
int n,root;
struct Node{
	int p,s,v;
	double avg;
}nodes[N];
int find(){
	int res=-1;
	double avg=0;
	for(int i=1;i<=n;i++){
		if(i!=root&&avg<nodes[i].avg){
			res=i;
			avg=nodes[i].avg;
		}
	}
	return res;
}
int main(){
	cin>>n>>root;
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>nodes[i].v;
		nodes[i].avg=nodes[i].v;
		nodes[i].s=1;
		ans+=nodes[i].v;
	}
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		nodes[b].p=a;
	}
	for(int i=0;i<n-1;i++){
		int p=find();
		int father=nodes[p].p;
		ans+=nodes[p].v*nodes[father].s;
		nodes[p].avg=-1;
		for(int j=1;j<=n;j++){
			if(nodes[j].p==p){
				nodes[j].p=father;
			}
		}
		nodes[father].v+=nodes[p].v;
		nodes[father].s+=nodes[p].s;
		nodes[father].avg=(double)nodes[father].v/nodes[father].s;
	}
	cout<<ans<<endl;

	return 0;
}