[CF1110G]Tree-Tac-Toe[博弈论、构造]

题目描述

两个人在一棵树上玩井字棋游戏，其中一个人是X，另一个人是O。游戏一开始是空的，每轮玩家可以在一个空格子里放置他的符号，当出现任意一方形成了一条长度为3的线（包括水平、竖直、对角线），这个人就赢了。

你需要编写一个程序来判断游戏是否结束，如果游戏结束，你需要输出胜利者的符号（'X'或'O'），如果游戏没有结束，你需要输出 "Draw"。

输入格式

第一行包含一个整数 n，表示树的节点的个数。

接下来 n-1 行每行描述一条边，包含两个整数 ui 和 vi，表示树上连接了节点 ui 和节点 vi。

输出格式

如果游戏结束，输出胜利者的符号（'X'或'O'），否则输出 "Draw"。

数据范围

1 ≤ n ≤ $10^5$

输入样例1

6
1 2
1 3
2 4
2 5
3 6

输出样例1

Draw

输入样例2

6
1 2
1 3
2 4
2 5
4 6

输出样例2

O

题目分析

树上博弈论，我们可以考虑用 SG 函数来做，但是 SG 函数的计算比较麻烦，需要考虑子树的 SG 值，我们考虑另外一种方式，直接判断胜负。

对于一个节点 u，我们先 DFS 计算节点 u 的子树中 X 和 O 的个数，设 X 数量为 cntx，O 数量为 cnto。那么对于其父亲节点 v，v 节点的胜负状态有以下几种情况：

- 如果 u 节点下有一颗子树中有三个 X，或者有三个 O，那么当前局面就结束了，胜利者为这颗子树中的 X 或 O。
- 如果 u 节点下有一颗子树中有两个 X，或者有两个 O，那么 u 和 u 的子树中除了这颗子树外的所有子树都可以随意选择 X 或 O，所以这颗子树中的 X 或 O 不会影响最终结果，当前节点 v 的胜负状态和其它子树相同。
- 如果 u 节点下有一颗子树中有一个 X，或者有一个 O，那么 u 和 u 的子树中除了这颗子树外的所有子树都可以随意选择 X 或 O，所以这颗子树中的 X 或 O 不会影响最终结果，当前节点 v 的胜负状态取决于其它子树的胜负状态。

时间复杂度

$O(n)$

C++ 代码