Codeforces 1110G Tree-Tac-Toe (博弈论)

题目链接

https://codeforces.com/contest/1110/problem/G

题解

首先，若原树上 (u) 点有白子，有一个很妙的转化是可以新建 (3) 个新点 (u_1,u_2,u_3), 并连边 ((u,u_1)), ((u_1,u_2)), ((u_1,u_3)), 并且去掉原有的这个白子，和原问题是等价的。
然后考虑初始没有白子的情况，观察可得若存在一个点连接至少 (2) 个度数 (ge 3) 的点，或者度数为 (3) 且连接至少 (2) 个度数 (ge 2) 的点，或者度数至少为 (4)，那么先手必胜。
在其余情况下，我们可以看出 (3) 度点的个数一定不超过 (2) 个，否则一定存在一个三度点连接至少 (2) 个二度点。那么图一定是一条链在从左到右或从右到左的第二个节点处挂了个叶子这种形态。
若存在 (2) 个三度点，这就相当于一条长为 ((n-4)) 且两端初始为白的链。若链的长度为奇数，那么白方每次染距离一端为 (2) 的点，必胜；若链长为偶数，平局；若三度点个数为 (0) 或 (1)，平局。
时间复杂度 (O(n)).

代码

#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define riterator reverse_iterator
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int N = 2e6;
struct Edge
{
	int v,nxt;
} e[(N<<1)+3];
int fe[N+3];
int du[N+3];
char a[N+3];
int dep[N+3];
int n,en;

void addedge(int u,int v)
{
	en++; e[en].v = v; du[u]++;
	e[en].nxt = fe[u]; fe[u] = en;
}

void dfs(int u,int tfa)
{
	for(int i=fe[u]; i; i=e[i].nxt)
	{
		int v = e[i].v; if(v==tfa) continue;
		dep[v] = dep[u]+1;
		dfs(v,u);
	}
}

int main()
{
	int T; scanf("%d",&T); while(T--)
	{
		scanf("%d",&n);
		for(int i=1; i<n; i++) {int u = read(),v = read(); addedge(u,v),addedge(v,u);}
		scanf("%s",a+1);
		for(int i=n; i>=1; i--)
		{
			if(a[i]=='W')
			{
				n+=3; addedge(i,n-2),addedge(n-2,i); addedge(n-2,n-1),addedge(n-1,n-2); addedge(n-2,n),addedge(n,n-2);
			}
		}
		bool flg1 = false;
		for(int i=1; i<=n; i++)
		{
			if(du[i]>=4) {flg1 = true; break;}
			int cnt2 = 0,cnt3 = 0;
			for(int o=fe[i]; o; o=e[o].nxt)
			{
				int v = e[o].v;
				if(du[v]>=2) cnt2++;
			}
			if(du[i]>=3&&cnt2>=2) {flg1 = true; break;}
		}
		if(flg1) {puts("White");}
		else
		{
			int cnt3 = 0;
			for(int i=1; i<=n; i++) if(du[i]==3) {cnt3++;}
			if(cnt3<=1) {puts("Draw");}
			else
			{
				int u = 0,v = 0;
				for(int i=1; i<=n; i++) {if(du[i]==3) {if(u==0) u = i; else v = i;}}
				dep[u] = 0; dfs(u,0);
				if(dep[v]&1) {puts("Draw");}
				else {puts("White");}
			}
		}
		for(int i=1; i<=en; i++) e[i].v = e[i].nxt = 0;
		for(int i=1; i<=n; i++) du[i] = dep[i] = fe[i] = 0;
		en = 0;
	}
	return 0;
}