【Codeforces Round #411 (Div. 1)】Codeforces 804C Ice cream coloring

本来图的$m$着色问题是只能状压dp$3^n$求解的，但是题上有一个很奇怪的条件，相同种类的冰激凌构成一个联通块。也就是说如果$1$和$2$、$3$在不同的点共同出现，那么$2$和 3 <script id="MathJax-Element-392" type="math/tex">3</script>一定不会在某个点共同出现。于是我们可以直接暴力dfs，在每个点对没有颜色的冰激凌贪心染最小的颜色。
需要注意有某种冰激凌没有出现的情况。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=300010;
int fir[maxn],ne[2*maxn],to[2*maxn],vis[maxn],clr[maxn],s[maxn],n,m,ans;
vector<int> v[maxn];
void add(int num,int x,int y)
{ne[num]=fir[x];fir[x]=num;to[num]=y;
}
void dfs(int u,int f)
{int now=1;for (vector<int>::iterator it=v[u].begin();it!=v[u].end();it++)if (clr[*it]) vis[clr[*it]]=u;for (vector<int>::iterator it=v[u].begin();it!=v[u].end();it++)if (!clr[*it]){while (vis[now]==u) now++;clr[*it]=now;ans=max(ans,now);vis[now]=u;}for (int i=fir[u];i;i=ne[i])if (to[i]!=f) dfs(to[i],u);
}
int main()
{int x,y;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d",&s[i]);for (int j=1;j<=s[i];j++){scanf("%d",&x);v[i].push_back(x);}}for (int i=1;i<n;i++){scanf("%d%d",&x,&y);add(i*2,x,y);add(i*2+1,y,x);}dfs(1,-1);if (!ans) ans=1;printf("%d\n",ans);for (int i=1;i<=m;i++)printf("%d%c",clr[i]?clr[i]:1,i==m?'\n':' ');
}