CodeForces 805E Ice cream coloring

直觉，构造。

画了几个样例，发现可以随便构造......先构造根节点的完全图，每个点置为不同的颜色，然后构造儿子节点的完全图......

#include <cstdio>

#include <cmath>

#include <set>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

int n,m;

const int maxn = 300010;

vector<int>g[maxn];

vector<int>d[maxn];

int f[maxn];

int ans[maxn],sz;

int t[maxn];

void dfs(int x)

{

	f[x]=1;

	int now = 1;

	for(int i=0;i<d[x].size();i++)

	{

		int col = d[x][i];

		t[ans[col]]=1;

	}

	for(int i=0;i<d[x].size();i++)

	{

		int col = d[x][i];

		if(ans[col]) continue;

		while(1)

		{

			if(t[now]) now++;

			else

			{

				ans[col] = now;

				t[now]=1;

				now++;

				break;

			}

		}

	}

	for(int i=0;i<d[x].size();i++)

	{

		int col = d[x][i];

		t[ans[col]]=0;

	}

	for(int i=0;i<g[x].size();i++)

	{

		int to = g[x][i];

		if(f[to]) continue;

		dfs(to);

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

	{

		int sz; scanf("%d",&sz);

		while(sz--)

		{

			int w; scanf("%d",&w);

			d[i].push_back(w);

		}

	}

	for(int i=1;i<n;i++)

	{

		int u,v; scanf("%d%d",&u,&v);

		g[u].push_back(v);

		g[v].push_back(u);

	}

	dfs(1);

	for(int i=1;i<=m;i++)

	{

		if(ans[i]==0) ans[i] = 1;

	}

	for(int i=1;i<=m;i++) sz = max(sz,ans[i]);

	printf("%d\n",sz);

	for(int i=1;i<=m;i++) printf("%d ",ans[i]);

	printf("\n");

	return 0;

}