11.给树染色 Color a tree

阅读数: 次 2020-11-17

字数：1.6k字 | 预计阅读时长：6分钟

作者：H_D_NULL

题目链接：SP3912 MTREECOL - Color a tree

题意

给定一棵树以及每个结点的权值 $v_i$，要求对所有点进行染色，条件是这个点的父节点已被染色，根节点第一个染色。染色的代价为染到这个点的时间 $T* v_i$，要求合理选出一种染色顺序（不用输出），使染色的代价和最小。

（比如对于一棵退化成链的树 $1->2->3$，染色顺序确定为 $1->2->3$，代价总和为 $1\times v_1+2\times v_2+3\times v_3$）

思路

在树上求代价，首先考虑树形 DP ，但是因为染色顺序没有规律，会对 DP 产生后效性，故排除，那么找到这种问题最佳策略的方法大概率为贪心；

先思考如果没有树结构的限制，那么最优方案肯定是按权值从大到小的顺序选，所以很容易想到两个错误的贪心策略，以下是错误示范和hack：

在所有可染的结点中选择权值最大的。hack：可选一个较小的结点，子树中有很多大结点，另外可选一个稍大的结点，没有子树；

在所有结点中选择权值最大的。hack：可选一个较小的结点，子树中有一个很大的结点，但是深度巨大，子树中其他结点很小，另外可选一个比刚刚的大结点稍小的结点；

不难发现，以上两个解法的错误都是因为没有考虑树结构限制染色顺序，针对某个点的权值，进而无法保证按顺序贪心的代价最小。

到这里，肯定有人（~~大概不是你~~）会敏锐地发现：“那如果一个点的即是权值最大的，又是现在可选，那一定选它吧。”没错，由这个结论，我们又可以引出一个重要的结论：如果一个点的权值最大，那么它一定在其父节点之后紧接着被染色。

那么有人（~~就是你了~~）多半会问：“这样只能确定这两个点的染色顺序，那么如何确定其父节点的染色时间呢？”虽然暂时无法解决这个问题，但是这给我们提供了一个思路，及将两个点甚至多个点视为一个整体，再针对这个点集的权值来确定贪心策略。

设最大点的权值 $x$ ，其父节点的权值 $fa$ 与另一点的权值 $y$ ，满足先选染最大点优于先选另一点的条件是：

$T\times fa+(T+1)\times x+(T+2)* y \leq T\times y+(T+1)\times fa+(T+2)* x$

$\iff x+2y \leq fa+2x$

$\iff y \leq (fa+x)/2$

那么结论就很显然了，对于这样两个点的点集，我们可以用 $(v_a+v_b)/2$ 来代替它的权值，那么推广得，对于一个 $k$ 个点的点集 $U$，我们定义它的等价权值$(\displaystyle\sum_ {i\in U} v_i)/k$ 。

贪心策略即是每次找到等价权值最大的点集，将它与它的父节点（集）合并为一个点集，直到只剩下一个点集（为了方便，我将这个点规定为根节点，具体见代码），每次枚举的复杂度为 $O(n^2)$ ，可以通过这道题，加堆维护后降为 $O(n log n)$，本人跑了 0ms，但是因为我处理合并时没有使用并查集，而是把合并时的父亲向儿子的所有儿子都连了一条边，导致常数很大，所以没有排到第一。

值得注意的是，这里的等价权值和染色的代价无直接关系，所以我们还需要存下每个点集的选点顺序，具体操作为每合并两个点集，就将儿子的合并顺序接在父亲的合并顺序之后，统计答案时按着顺序模拟一遍即可，具体见代码。

Talk is cheap, show me the code

#include<bits/stdc++.h>
#define re register
using namespace std;
const int N=1005;

inline int read(){
	re int ret=0;
	re char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9'){
		ret=(ret<<1)+(ret<<3)+(c^48);
		c=getchar();
	} return ret;
}

int n,root,fa[N],ans;
int a[N],st[N],num[N],T;

vector <int> que[N]; //处理每个点集的合并顺序 

inline void Solve(int k){
	T++; ans+=st[k]*T;
	for(re auto l:que[k]) Solve(l);
} //采用递归的方式还原顺序 

bool vis[N];

struct Edge{
	int nxt;
	int to;
} e[N*N>>1];
//按照我的暴力合并方式，需要多开边 

int h[N],cnt;

inline void add(int x,int y){
	e[++cnt].nxt=h[x];
	e[cnt].to=y;
	h[x]=cnt;
}

struct R{
	int id,val,cnt;
	//id:结点编号（用点集中最高的结点代替整个点集）
	//val:权值和 
	//cnt:结点数 
};

struct cmp{
	bool operator ()(const R &x,const R &y) const{
		return x.val*y.cnt<x.cnt*y.val;
	} //其实我觉着吧，还是要开 long long 的 
};

priority_queue <R,vector<R>,cmp> q;

int main(){
	while(true){
		n=read(); root=read(); if(!n&&!root) break;
		T=fa[root]=cnt=ans=0;
		for(re int i=1;i<=n;i++){
			a[i]=st[i]=read();
			h[i]=vis[i]=0; que[i].clear(); num[i]=1;
			if(i!=root) q.push((R){i,a[i],1});
			//因为最后目的是合并到根上，所以不合并根节点 
		}
		for(re int i=1,x,y;i<n;i++){
			x=read(); y=read();
			add(x,y); fa[y]=x;
		}
		while(!q.empty()){
			re R x=q.top(); q.pop();
			if(x.val!=a[x.id]) continue;
			//代替删除操作：如果这个点的信息“过期”，视为已被删除 
			re int now=x.id,mas=fa[now];
			vis[now]=1; //表示其是否已经被当作一个子结点合并过了 
			a[mas]+=x.val; num[mas]+=x.cnt;
			que[mas].push_back(now);
			//处理顺序，只存代表点集的点编号，最后递归查找 
			if(mas!=root) q.push((R){mas,a[mas],num[mas]});
			for(re int i=h[now],to;i;i=e[i].nxt){
				to=e[i].to; if(vis[to]) continue;
				fa[to]=mas; add(mas,to); //暴力加边 
			}
		}
		Solve(root);
		printf("%d\n",ans);
	}
	return 0;
}

本文作者： 益题 Yitee
发布时间： 2020-11-17
最后更新： 2021-08-19
本文标题： 11.给树染色 Color a tree
本文链接： https://yitee.top/posts/261.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明出处！