1110G - Tree-Tac-Toe - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int dfs(int x, int f, const vector<vector<int>> &G, char* c, vector<bool> &vis, int &ans) {
	if (vis[x]) return -1;
	vis[x] = true;
	if (ans) return -1;

	int ws = -1;

	int cw = (c[x] == 'W' || ws != -1);
	int rt = 0, c0 = 0, c1 = 0;
	for (int y : G[x]) {
		if (y == f || y == ws) continue;
		int ret = dfs(y, x, G, c, vis, ans);
		if (ret == 0) {
			if (cw && (G[x].size() >= 2 && ws == -1 || G[x].size() >= 3)) {
				ans = 1;
			}
			if (c0) ans = 1;
			rt += 1;
			c0 += 1;
		} else if (ret == 1) {
			ans |= cw;
			if (c1) ans = 1;
			c1 += 1;
			rt += 1;
		}
	}

	if (!rt && !cw) return -1;
	return c0 ? 1 : 0;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		int n;
		scanf("%d", &n);
		vector<vector<int>> G(n);
		vector<int> nc(n), ss(n), aw(n);
		vector<bool> vis(n);
		for (int i = 0; i < n - 1; ++i) {
			int x, y;
			scanf("%d %d", &x, &y);
			x -= 1;
			y -= 1;
			G[x].push_back(y);
			G[y].push_back(x);
		}

		int ans = 0;
		auto c = unique_ptr<char[]>(new char[n + 1]);
		scanf("%s", c.get());
		for (int x = 0; x < n; ++x) {
			if (G[x].size() >= 4) goto WW;
		}

		for (int x = 0; x < n; ++x) {
			for (int y : G[x]) {
				ss[x] += (G[y].size() > 1);
				if (c[y] == 'W') continue;
				for (int z : G[y]) {
					if (z == x) continue;
					if (G[z].size() >= 3) goto NL;
				}
				nc[x] += 1;
NL:
				;
			}

			int m = G[x].size(), wc = m - nc[x];
			if (m >= 4 || c[x] == 'W' && m >= 3) goto WW;
			if (wc >= 2 || wc == 1 && c[x] == 'W' && nc[x] >= 1) goto WW;
			if (wc == 1 && nc[x] >= 2) goto WW;
		}

		for (int x = 0; x < n; ++x) {
			int m = G[x].size();
			if (c[x] == 'W') {
				if (ss[x] >= 1 && m >= 2) goto WW;
			} else {
				if (ss[x] >= 2 && m >= 3) goto WW;
			}
		}

		for (int x = 0; x < n; ++x) {
			for (int i = 0; i < (int)G[x].size(); ++i) {
				int y = G[x][i];
				int cn = 0;
				for (int z : G[y]) {
					if (z == x) continue;
					if (G[z].size() > 1) cn = -10;
					cn += 1;
				}
				if (cn == 2) {
					G[x].erase(G[x].begin() + i);
					for (int j = 0; j < (int)G[y].size(); ++j) {
						if (G[y][j] == x) {
							G[y].erase(G[y].begin() + j);
							break;
						}
					}
					c[x] = 'W';
					break;
				}
			}
		}

		for (int i = 0; i < n; ++i) dfs(i, -1, G, c.get(), vis, ans);
		if (ans) WW: puts("White");
		else puts("Draw");
	}
	return 0;
}