Game on a Tree（博弈+树形dp）

题目链接：http://codeforces.com/gym/102392/problem/F 参考题解：http://codeforces.com/gym/102392/problem/F 题意：给定一棵根结点为 的树，一开始全白，alice和bob轮流玩，Alice选择一个点，将其染黑，接下来Bob将这个点的某个祖先点或其子树点染黑，2个人轮流来，双方都采取最优策略，问最终谁获胜 题解：dp表示当前点剩下的最少未匹配点，cnt为 ∑ d p [ v ] \sum{dp[v]} ∑dp[v]，则有当cnt=0时，dp[u]=1;cnt>0时，dp[u]=cnt-1。当dp[1]为0时，说明该树完美匹配，完美匹配则Bob胜利，否则Alice胜利。

#include
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn=100010;

int n;
int head[maxn],tot;
struct edge{
    int v,nxt;
}e[maxn*2];
void init(){
    tot=0;
    for(int i=0;i