CF804C Ice cream coloring 做题记录

有一颗 $n$ 个节点的树 $T$ 和 $m$ 种冰淇淋，树上的第 $i$ 个节点有 $s_i$ 个冰淇淋，且所有相同种类的冰淇淋在树上构成了一个联通块。

构造一个新的图 $G$ ，$G$ 有 $m$ 个节点，$G$ 中的 $u,v$ 之间有边，当且仅当存在至少一个在 $T$ 上的节点满足他同时有第 $u$ 种和第 $v$ 种冰淇淋。

你的任务是用尽可能少的颜色种类数给 $G$ 的每一个节点染色，使得没有两个相邻的节点有相同的颜色，要求输出方案。

注意空的点集也被认为是一个联通块。

$1\le n,m\le 3\times 10^{5}$，$0\le s_{i}\le 3\times 10^{5}$，$\sum s_i\le 5\times 10^5$。

不难发现，由于每个节点上的冰淇淋种类一定构成了一张完全子图，所以颜色数量下界为 $\max\limits_{i=1}^n s_i$，猜测答案一定能取到这个下界，尝试证明之。

尝试归纳证明：

1. 首先有且仅有一个根节点的树是合法的；
2. 考虑根节点 $rt$，假设它的所有儿子的子树都合法，那么因为同种冰淇淋是连通的所以两端冰淇淋颜色相同的边的两端的冰淇淋一定都在 $rt$ 上出现过，颜色一定够用；

综上，证毕。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

const int S=1000005;

int n,m,mx;
vector<int> col[S];
int esum,to[S],nxt[S],h[S];
int ans[S];

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

void dfs(int u,int fa)
{
	set<int> st;
	for(int v:col[u]) st.insert(ans[v]);
	int cnt=1;
	for(int v:col[u])
	{
		if(ans[v]==0)
		{
			while(st.count(cnt)) cnt++;
			ans[v]=cnt;
			st.insert(cnt);
		}	
	}
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	mx=1;
	for(int i=1;i<=n;i++)
	{
		int cnt;
		scanf("%d",&cnt);
		mx=max(mx,cnt);
		while(cnt-->0)
		{
			int x;
			scanf("%d",&x);
			col[i].push_back(x);
		}
	}
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	dfs(1,0);
	printf("%d\n",mx);
	for(int i=1;i<=m;i++) printf("%d ",ans[i]==0?1:ans[i]);
	printf("\n");
	return 0;
}