Codeforces #411 Div1 C. Ice cream coloring

なんでアイスクリームなんだ？
http://codeforces.com/contest/804/problem/C

問題

N頂点からなる木を成すグラフがある。
各頂点には、いくつかのアイスクリームが購入可能であり、その種類は入力として与えられる。
なお、同じアイスクリームが購入可能な頂点同士は互いに連結である。

ここで、各アイスクリームを最小数の色で彩色せよ。
ただし、同一の頂点で購入可能なアイスクリーム間は同じ色を用いてはならない。

解法

最小の色数は、各頂点における購入可能なアイスクリーム種別の最大数に一致する。

種別が最大の頂点からDFSし、その際未彩色のアイスクリームに当たったら未使用の色の値の最小値を用いる、という手順で彩色すればよい。
「同じアイスクリームが購入可能な頂点同士は互いに連結である。」という条件より、根から順にDFSしながら彩色する際、「今適当な色を設定してしまったおかげであとで困る」ということは発生しない。
(親頂点で購入不可能で、現頂点で購入可能なアイスクリームは、必ず未彩色であるため)

int N,M;
vector<int> S[303030];
vector<int> E[303030];
int color[303030];

void dfs(int cur,int pre) {
	set<int> C;
	FORR(s,S[cur]) if(color[s]) C.insert(color[s]);
	
	int x=1;
	FORR(s,S[cur]) if(color[s]==0) {
		while(C.count(x)) x++;
		color[s]=x;
		C.insert(x);
	}
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	set<pair<int,int>> Q;
	int ma=0;
	FOR(i,N) {
		cin>>x;
		FOR(j,x) {
			cin>>y;
			S[i].push_back(y-1);
		}
		if(x>S[ma].size()) ma=i;
	}
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(ma,-1);
	
	FOR(i,M) if(color[i]==0) color[i]=1;
	_P("%d\n",*max_element(color,color+M));
	FOR(i,M) _P("%d%c",color[i],(i==M-1)?'\n':' ');
	
}

まとめ

結構悩んだけど、終わってみればあっさり。