题目链接：https://codeforces.com/contest/1110/problem/G
给你一棵树，其中一些点已经染上了白色，有的没有颜色
现在有两个玩家黑色，白色，白色为先手
他们可以在树上把没有染色的点染上自己的颜色，
胜利条件为形成一条有三个顶点为某人颜色的路径，
假设两人聪明绝顶，问最终是谁胜出或平手。
这道题一开始是想树形DP的，
可是状态不太好设，
转移也特别麻烦。
所以DP就弃了
但可以发现貌似能分类讨论来解决这道题。
手玩一下可以发现
如果有一个度数大于等于4的点，那白色必胜。
如果有一个度数为3的点，
且该点为白色或与之相连的点中有白色点，则白色必胜。
或者是与之相连的点中有两个度数都大于等于2，则白色必胜。
如果有一个度数为2的点，
且该点以及与之相连的点中有两个白色点，则白色必胜。
如果树的形态是一条链，且链的非边缘部分有白色点，则白色必胜
去掉以上的情况以后，
树的形态要么是一条链，要么是一条两端有度数为3的点的类似链的情况，
考虑到链中除度数为3的点中最靠近度数为3的点可以转化为白点。
剩下的情况就只有这么一种，
一个链，只有边缘部分被染成白色。
那么，显然
如果不是两端都为白色的话，必定平手
而两端如果都是白色，那么只有长度为奇数的，白色才会胜利。
反之平手
CodeForces 1110 G. Tree-Tac-Toe
原文：https://www.cnblogs.com/JY-Chen/p/13636151.html