color a tree(贪心)
题目描述
可以得到一个确定性的结论，最大值的结点一定是在父节点染色后立即染色。
但是此时依结论不好在复杂的情况正推，先考虑简单情况：
假如有权值x,y,z三个点，已知x,y一定一起染色，则有两种可能方案：
- 先x,y,再z，代价为X=x+2y+3z
- 先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;
}