本文共 1756 字，大约阅读时间需要 5 分钟。
描述
小Hi和小Ho经常一起结对编程，他们通过各种对弈游戏决定谁担任Driver谁担任Observer。
今天他们的对弈是在一棵有根树 T 上进行的。小Hi和小Ho轮流进行删除操作，其中小Hi先手。
游戏的规则是：每次删除，小Hi或小Ho都可以选择一个非根节点，将以该节点为根的子树从 T 中删除。如果删除之后 T 只剩下一个根节点，则该次操作者胜利。
机智的小Ho认为规则对自己不利，于是他提出了一个补充规则：在小Hi第一次删除之前，小Ho可以选择是否删除根节点。如果他选择删除根节点，则原本的有根树 T 会分裂成一个森林。之后每次删除，小Hi或小Ho都可以选择一个非根节点（不是森林中任何一棵树的根），将以该节点为根的子树删除。如果删除之后森林中只剩下根节点，则该次操作者胜利。
小Hi和小Ho都是睿智的玩家，他们总是会选择最优的方案以获得胜利。
给定初始的有根树T，输出两个布尔值，分别代表小Ho在不删除和删除根节点时，先手的小Hi是否有必胜策略。0代表没有，1代表有。
输入
第一行包含一个整数 Q，代表测试数据的组数。1 ≤ Q ≤ 10
对于每组数据，第一行包含一个正整数 n，代表树T的节点个数。1 ≤ n ≤ 100000
接下来n-1行，每行包含两个整数 x 和 y，代表 x 是 y 的父节点。保证输入是一棵树，节点编号1-n。
输出
输出一个长度为2Q的01串，代表答案。
样例输入 -
252 55 42 31 274 72 61 53 41 31 2
样例输出 -
1101
一道博弈题，首先找规律发现：一棵树的情况下，给每个点赋值1，对于每个节点，将自己子节点的值取异或后加上自己的值，最后判断根节点的值是否大于0，大于0则一定存在必胜，否则不存在；对于森林的情况直接相互取异或即可。
#include using namespace std;const int MX = 1e5 +5;struct Edge{ int v,nxt;}E[MX*2];int head[MX],IN[MX],tot,n,T;void init(){ memset(IN,0,sizeof(IN)); memset(head,-1,sizeof(head)); tot=0;}void add(int u,int v){ E[tot].v=v; E[tot].nxt=head[u]; head[u]=tot++; IN[v]++;}int root;int dfs(int u){ int ret=0; for(int i=head[u];~i;i=E[i].nxt){ int v=E[i].v; ret^=dfs(v); } return ret+(u!=root?1:0);}int rt;int dfs2(int u){ int ret=0; for(int i=head[u];~i;i=E[i].nxt){ int v=E[i].v; ret^=dfs2(v); } return ret+(u!=rt?1:0);}int main(){ //freopen("in.txt","r",stdin); scanf("%d",&T); while(T--){ init(); scanf("%d",&n); for(int i=1,u,v;i 0?1:0); int ans2=0; for(int i=head[root];~i;i=E[i].nxt){ rt=E[i].v; ans2^=dfs2(rt); } printf("%d",ans2>0?1:0); } printf("\n"); return 0;}
转载地址：http://bpwpn.baihongyu.com/