Codeforces Global Round 1 : G. Tree-Tac-Toe

一見単純で地味にややこしい問題。
https://codeforces.com/contest/1110/problem/G

問題

木を成す頂点が与えられる。
各頂点は無色か白色に塗られている。
この木を使い三目並べを行う。白側が先手のとき、両者最善手を打つと勝者はどちらか。

解法

先手が白でもともと白で塗られた頂点があるので、黒が勝つことはありえない。
よって白が勝つか引き分けかを求めよう。

元々白色と無色の箇所があると面倒なので、全部無色に置き換えてしまおう。
白色頂点○は、以下の無職の４頂点に置き換えることができる。
●はもともと○のあった箇所を置き換えるもので、そこに☆頂点が追加される。

●-☆-☆
    |
   ☆

というのも先手が●を白く塗ると、後手は隣を塗らないと負けるので必ず塗ることになるので、最適手を取る過程で結局●は白く塗られるためである。

あとが全頂点無色の場合を考える。とはいえ愚直にパターンを列挙していけばよい。

• 次数４以上の頂点がある。
• 次数３の頂点があるとき、その隣接頂点のうち２つ以上が次数２以上である。
• 次数３の頂点が２個あるとき、その距離が偶数である。

これ以外は引き分けとなる。

int T;
int N;
vector<int> E[2505050];
string S;
int P[2505050];
int C[2];

void dfs(int cur,int col,int pre) {
	if(E[cur].size()==3) C[col]++;
	FORR(e,E[cur]) if(e!=pre) dfs(e,col^1,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,4*N) E[i].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		cin>>S;
		int ok=0;
		x=N;
		FOR(i,N) if(S[i]=='W') {
			E[i].push_back(x);
			E[x].push_back(i);
			E[x].push_back(x+1);
			E[x].push_back(x+2);
			E[x+1].push_back(x);
			E[x+2].push_back(x);
			x+=3;
		}
		N=x;
		FOR(i,N) {
			if(E[i].size()>=4) ok=1;
			if(E[i].size()>=3) {
				int num=0;
				FORR(e,E[i]) if(E[e].size()>=2) num++;
				if(num>=2) ok=1;
			}
		}
		C[0]=C[1]=0;
		dfs(0,0,-1);
		if(C[0]>=2 || C[1]>=2) ok=1;
		
		
		if(ok) {
			cout<<"White"<<endl;
		}
		else {
			cout<<"Draw"<<endl;
		}
		
	}
}

まとめ

最後のケースがわからなかった。