题目大意：
给你一棵树，两人轮流染色。 先手染白色，后手染黑色。 当整个树染完时，与黑色相邻的白色点变成黑色。 两人都按照最优策略进行染色。 如果最后还有白色，那么是先手胜，否则是后手胜。思路：
贪心。 题目问的实际上就是，如果两人都按照最优策略染色，存不存在一种情况，使得存在一个白色结点不与黑色结点相邻。 一个显而易见的最优策略是，先手选了一个点，且这个点周围没有黑色点，后手一定要选一个和它相邻的点。 同样，先手不会选择已经与黑色点相邻的点。 这就变成了一个完美匹配问题，题目所求即为原树中是否存在一个完美匹配，如果是，则说明先手必败。 如果存在完美匹配，那么不管先手怎么下，后手都能找到一个匹配上的点。 如果不存在完美匹配，那么先手就可以下在这个点上，然后不管后手怎么下，它都总能找到一个点不会与黑点相邻，先手胜。 于是我们可以贪心地从下往上贪心地构造完美匹配。 如果一个结点有多个子结点需要匹配，那么肯定只能匹配到其中一个，也就是说无法构造完美匹配，先手胜。 如果根结点需要匹配，那么也没有结点能和它匹配，无法构造完美匹配，先手胜。1 #include2 #include 3 #include 4 #include 5 inline int getint() { 6 register char ch; 7 while(!isdigit(ch=getchar())); 8 register int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10 return x;11 }12 const int N=100001;13 std::vector e[N];14 inline void add_edge(const int &u,const int &v) {15 e[u].push_back(v);16 e[v].push_back(u);17 }18 inline bool dfs(const int &x,const int &par) {19 int ret=0;20 for(unsigned i=0;i