题解：P16560 [ICPC 2026 APC] Subtree Removal Game

· · 题解

题意简述

两人轮流删除一棵有根树的某个子树，但必须保证至少一个原叶子仍存在。最终留下的原叶子编号就是得分。先手希望最小化得分，后手希望最大化得分，求双方最优策略下的结果。

解题思路

二分最终得分。固定一个编号 x，把编号不超过 x 的原叶子称为小叶子，其余称为大叶子。现在只需判断先手能否保证最后留下小叶子。

对每个节点 u 定义状态 d_u。若 u 是原叶子，则：

d_u= \begin{cases} 1 & u\le x \\ -1 & u>x \end{cases}

若 u 不是原叶子，先求出所有儿子状态之和 s_u，再令：

d_u= \begin{cases} 1 & s_u>0 \\ 0 & s_u=0 \\ -1 & s_u<0 \end{cases}

下面说明这个状态的含义。考虑只保留以 u 为根的子树，并指定当前行动者：

可以对原叶子数量归纳证明。若儿子状态之和为正，先手行动时可删除一个非正儿子；若所有儿子都为正，则任意删除一个儿子后总和仍非负。后手行动一次只会让总和减少至多 1，不能把正值直接变成负值。状态之和为负时完全对称。

当状态之和为 0 时，先看当前节点的儿子。若正、负儿子同时存在，当前行动者可以删除对手一侧。否则沿着状态为 0 的儿子向下走。最终会到达同时存在正、负儿子的节点，故结论仍成立。

于是，对固定的 x，先手获胜当且仅当 d_1\ge 0。随着 x 增大，叶子状态只会从 -1 变成 1。所有节点状态均单调不减。故最小的可行 x 可以二分得到，它就是答案。

题目保证父节点编号小于子节点编号。按编号从大到小处理，即可完成一次树形递推。单次判断为 O(n)。总时间复杂度为 O(n\log n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int> p(n+1),cnt(n+1);
    for(int i=2;i<=n;i++)
    {
        cin>>p[i];
        cnt[p[i]]++;
    }
    vector<int> sum(n+1),d(n+1);
    auto check=[&](int x)
    {
        fill(sum.begin(),sum.end(),0);
        for(int i=n;i>=1;i--)
        {
            if(!cnt[i])d[i]=i<=x?1:-1;
            else d[i]=(sum[i]>0)-(sum[i]<0);
            if(i>1)sum[p[i]]+=d[i];
        }
        return d[1]>=0;
    };
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
    return 0;
}