大体思路
由于某个节点的操作取决于子树内的操作次数，我们定义“奇子树”为一个操作完整个子树的次数为奇数的子树，“偶子树“类似。
首先有一个很经典的 trick：采用二分，凡是大于等于判定值的赋为 $1$，否则为 $0$，则问题变成了值只有 $0,1$ 的问题。
如果一棵树是“奇子树”，则先手能进行最后一步操作，此时两个子树中只要有一个 $1$ 先手即可获胜。如果一棵树是“偶子树”的话，后手进行最后一步操作，仅当两个子树均为 $1$ 时先手才能获胜。
最简单的情况是一个节点的两个子树均为“偶子树”。此时如果后手在先手必胜的子树内操作，先手有必胜策略，否则先手随便选即可保证自己的胜利。
但是当一个节点的两个子树均为“奇子树“时，我们发现这个策略不管用了。因为先手无法通过跟着后手选来消耗步数，维持自己的必胜态。此时仅当先手”停一步“后仍能胜利才能获得最终的胜利。
因此采用 DP：$f_{u,(0/1),(0/1/2)}$ 表示在 $u$ 子树内，当前是先/后手，两个儿子的状态是两个偶数/两个奇数/一奇一偶的答案。
分类讨论转移
接下来到了喜闻乐见的大分讨环节。首先把两个儿子都是叶子的情况特判掉。由于当前为后手的情况完全等同于当前为先手情况的相反操作，我们只考虑当前为先手的情况。
这样这道题就做完了。
代码实现
看上去也不是很困难，对吗？放一下 DP 转移的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| if(sz[rid]&1)swap(lid,rid);
if(!(sz[u]&1)){
f[u][0][0]=(f[lid][0][0]&&f[rid][1][0])||(f[lid][1][1]&&f[rid][0][1]);
f[u][1][0]=(f[lid][1][0]||f[rid][0][0])&&(f[lid][0][1]||f[rid][1][1]);
for(int i=1;i<=2;i++){
f[u][0][i]=f[lid][0][(!sz[rid]&&i==1)?2:1]||f[rid][0][0];
f[u][1][i]=f[lid][1][(!sz[rid]&&i==1)?2:1]&&f[rid][1][0];
}
}
else {
f[u][0][0]=f[lid][0][sz[lid]&1]||f[rid][0][sz[rid]&1];
f[u][1][0]=f[lid][1][sz[lid]&1]&&f[rid][1][sz[rid]&1];
for(int i=1;i<=2;i++){
f[u][0][i]=f[u][1][0],f[u][1][i]=f[u][0][0];
if(sz[lid]&1){
f[u][0][i]|=(f[lid][0][0]&&f[rid][1][(sz[lid]==1&&i==1)?2:1])||(f[lid][1][(sz[rid]==1&&i==1)?2:1]&&f[rid][0][0]);
f[u][1][i]&=(f[lid][1][0]||f[rid][0][(sz[lid]==1&&i==1)?2:1])&&(f[lid][0][(sz[rid]==1&&i==1)?2:1]||f[rid][1][0]);
}
else{
if(sz[lid]){
f[u][0][i]|=f[lid][0][(!sz[rid]&&i==1)?2:1]&&f[rid][1][0];
f[u][1][i]&=f[lid][1][(!sz[rid]&&i==1)?2:1]||f[rid][0][0];
}
if(sz[rid]){
f[u][0][i]|=f[lid][1][0]&&f[rid][0][(!sz[lid]&&i==1)?2:1];
f[u][1][i]&=f[lid][0][0]||f[rid][1][(!sz[lid]&&i==1)?2:1];
}
}
}
}
|
对了，实际实现的时候，可以把 $0,1$ 序列的操作直接变成取最小/最大值，从而省去一次二分。