Codeforces #403 Div1 A. Andryusha and Colored Balloons

Dまではいつもより簡単目。
http://codeforces.com/contest/781/problem/A

問題

N頂点からなる木を成すグラフが与えられる。
このグラフの頂点を彩色したい。
３頂点(A,B,C)がA-B-Cと辺でつながっているとき、その３頂点は異なる色でなければならないとする。
必要な色数の最小値を求め、塗り分けの一例を示せ。

解法

根付き木とみなし、根から順にDFSで色を確定させていく。
その際、各頂点ではsetでその頂点自身および隣接点の色の集合を保持しよう。

DFSをしていくとき、各頂点では親頂点およびその隣接頂点で未使用の色のうち最小値を求めればよい。
その際、毎回setを全探索して最小値を求めるとO(N^2)かかってTLEしかねないので、前回探索した範囲を再探索しないようにしよう。

int N;
vector<int> E[201010];
set<int> S[201010];
int C[201010],P[201010];
int ma;
void dfs(int cur,int pre) {
	if(pre!=-1) {
		while(S[pre].count(P[pre])) P[pre]++;
		C[cur]=P[pre];
		S[pre].insert(C[cur]);
		S[cur].insert(C[pre]);
	}
	S[cur].insert(C[cur]);
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	_P("%d\n",*max_element(C,C+N)+1);
	FOR(i,N) _P("%d ",C[i]+1);
	_P("\n");
}

まとめ

750ptでもいいかなと思った。