[数据结构与算法]Color a tree（贪心）

题目

原题链接

问题描述

一颗树有$n$个节点，这些节点被标号为$;1,2,3\dots n$，每个节点$i$ 都有一个权值 $A[i]$。
现在要把这棵树的节点全部染色，染色的规则是：
根节点 $R$ 可以随时被染色；
对于其他节点，在被染色之前它的父亲节点必须已经染上了色。
每次染色的代价为 $T\times A[i]$，其中 $T$ 代表当前是第几次染色。

求把这棵树染色的最小总代价。

分析

需要注意的是：根节点的序号为$R$，而不一定为1。

一个容易犯错的贪心策略就是从可以染色的点中选择权值最大的点，但不一定能满足最优的染色策略。
例如：

如果依照这个策略将得到$[12435]$的染色顺序，总代价为$35$，但最优染色策略为$[13524]$,所得总代价为$33$。

但再一种情况下，我们可以直接确定下一步的染色对象：也就是树中除根节点外权值最大的节点，在它的父节点被染色后，我们下一次就一定会对这个点进行染色。 因为不存在其他的更优的染色策略。

但如何将这一规律应用到题目中呢？

假设节点$X$正是满足我们要求的节点，它的权值正是所有未被染色的点中最大的，$X$的父节点为$Y$。
我们对$X,Y$的染色操作是连续的，所以我们可以将两步进行合并。

若此时存在一个节点$Z$，$Z$与$X$都满足染色的要求：
1.先染$Z$，$an{s}_1=Z+2?X+3?Y$
2.先染$XY$，$an{s}_2=X+2?Y+3?Z$
需要比较$an{s}_1,an{s}_2$的大小关系。
若$an{s}_1>an{s}_2$，$Z+2?X+3?Y>X+2?Y+3?Z$，即$\frac{X+Y}{2}>Z$;
若$an{s}_1\le an{s}_2$，即$\frac{X+Y}{2}\le Z$。

此时只需要比较$\frac{X+Y}{2}跟Z$的关系，所以不妨将$\frac{X+Y}{2}$作为合并后$X、Y$为一点后的等效权值。
将节点$Y$并入节点$X$后，需要将$Y$的所有子节点同时并入$X$的子节点才是真正的合并。

等效权值的推广：由于我们当初依照的是贪心的策略，其实也就是局部染色的顺序。
对于合并两个节点之前，两个节点很可能已经被合并过了，它们之前的合并说明之前的染色策略更优，我们引入两个值来描述它们的合并情况：
$Val（合并所有的点的权值总和）$
$num（合并的点的个数，初始化值为1）$
$\frac{Val}{num}$表示该点的等效权值。

我们合并满足上述要求的$X、Y$时：$ans+=X.Val?Y.num$。（Y为父）
表示在对$X$染色之后，需要先经过$Y.num$次染色才会对$X$进行染色，我们可以先对结果加上这一部分的值。

合并后：
$Y.Val+=X.Val$
$Y.num+=X.num$
$Y$的等效权值为$\frac{Y.Val}{Y.num}$
经过$n?1$次合并，我们将会得到一个合并了所有点的点，此时我们已经计算了合并过程中的染色代价，但还需要$ans+={\sum }_{i=1}^{n}a[i]$才是我们最后的答案，因为全部的染色过程不只是有合并过程的染色代价，在合并之前，我们需要对父节点进行染色，这一步之前没有被计算。

关于这个权值最大的点的选择可以暴力遍历，也可以维护一个优先队列，但优先队列不能在我们修改权值后自动及时更新，所以采用暴力会更方便一些。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
const ll N=1e3+5;
ll n,r,ans;
struct node{
	ll fa,num;
	double val;
	vector<ll>son;
};
node a[N];
ll find(){
	int ans;
	double maxn=0;
	fir(i,1,n){
		if(i!=r&&(a[i].val/a[i].num)>maxn){
			maxn=a[i].val/a[i].num;
			ans=i;
		}
	}
	return ans;
}
int main(){
	while(cin>>n>>r){
		if(!n&&!r)return 0;
		ans=0;
		fir(i,1,n){
			cin>>a[i].val;
			a[i].num=1;
			ans+=a[i].val;
			a[i].fa=0;
		}
		fir(i,1,n-1){
			ll x,y;
			cin>>x>>y;
			a[y].fa=x;
			a[x].son.push_back(y);
		}
		fir(i,1,n-1){
			ll tmp=find(); 
			ll Fa=a[tmp].fa;
			ans+=a[tmp].val*a[Fa].num;
			for(auto x:a[tmp].son){
				a[x].fa=Fa;
				a[Fa].son.push_back(x);
			}
			a[Fa].num+=a[tmp].num;
			a[Fa].val+=a[tmp].val;
			a[tmp].val=0;
		}
		cout<<ans<<endl;
	}
}
/*
5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0

33
*/