一、核心回顾（简单版结论依然成立）

1. 设所有叶子的最小深度为 $d$

$$d = \min\limits_{u\text{ 是叶子}} \text{dep}[u]$$

2. 答案上界 = $d$
3. 能取到 $d$ 的条件： 前 $d$ 层可以整体染 0 或 1，且使用的 0 的总数 $s$ 满足：

$$s \le k,\quad \text{sum} - s \le n-k$$

4. 做不到 $\Rightarrow$ 答案为 $d-1$。

---

二、困难版的核心挑战

简单版背包：

$$O(n^2)$$

$n=2\times 10^5$ 时完全超时。

必须优化：

优化思路

• 本题背包是 多重背包
• 每层大小是 $cnt[i]$，有若干个相同重量的物品
• 使用 二进制拆分 把多重背包转 01 背包
• 使用 bitset 把背包转移压到机器字级并行

最终复杂度：

$$O\left(\frac{n\sqrt{n}}{\omega}\right)$$

$\omega$ 是机器字长（64位），极快，可过 $2\times 10^5$。

---

三、标程核心算法

1. 预处理

• 求每个点深度 $\text{dep}[i]$
• 求每层节点数 $cnt[i]$
• 求叶子最小深度 $d$

2. 多重背包 → 二进制拆分

前 $d$ 层中，可能有很多层大小相同，例如： $cnt = [1,1,1,2,2,3]$

二进制拆分规则： 把 $t$ 个相同重量 $w$ 的物品拆成：

$$1\cdot w,\ 2\cdot w,\ 4\cdot w,\ \dots$$

最后剩下的单独一组。

拆分后物品总数从 $O(n)$ 降到 $O(\sqrt{n})$。

3. bitset 优化 01 背包

• $dp$ 是 bitset，$dp[i]=1$ 表示能凑出 $i$ 个 0
• 转移：

$$dp \mid= dp \ll val$$

一次操作处理一个物品，并行64位，速度爆炸。

4. 检查是否合法

存在 $i$ 满足：

$$dp[i]=1,\quad i\le k,\quad sum-i \le n-k$$

合法 $\Rightarrow$ 答案 $d$ 不合法 $\Rightarrow$ 答案 $d-1$

---

四、标程代码逐行详细解释

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

// 模板递归开 bitset 空间（自动扩容）
template <int maxn>
int solve(int n, int k) {
    if (maxn <= n) {
        return solve<min(N, maxn * 2)>(n, k);
    }

    bitset<maxn> dp;        // bitset背包
    vector<int> fa(n, -1), dep(n, 0);
    vector<int> noson(n, 1), cnt(n + 1);
    cnt[0]++;

    // 读入树结构，求深度、层数大小、叶子
    for (int i = 1; i < n; i++) {
        cin >> fa[i], fa[i]--;
        dep[i] = dep[fa[i]] + 1;
        cnt[dep[i]]++;
        noson[fa[i]] = 0;
    }

    // 求叶子的最小深度 d
    int mxdep = 1e9;
    for (int i = 0; i < n; i++)
        if (noson[i])
            mxdep = min(mxdep, dep[i]);

    // 取出前 d 层
    vector<int> all(cnt.begin(), cnt.begin() + mxdep + 1);
    sort(all.begin(), all.end());  // 相同重量放一起

    vector<int> v;
    // 二进制拆分多重背包
    for (int i = 0; i < (int)all.size(); i++) {
        int j = i;
        while (j + 1 < (int)all.size() && all[i] == all[j + 1])
            j++;
        int t = j - i + 1;  // t 个相同重量 all[i]

        // 二进制拆分
        for (int z = 1; z <= t; z *= 2) {
            v.push_back(z * all[i]);
            t -= z;
        }
        if (t > 0)
            v.push_back(t * all[i]);
        i = j;
    }

    // bitset 背包
    dp.reset();
    dp[0] = 1;
    int sum = 0;
    for (auto val : v) {
        sum += val;
        dp |= (dp << val);  // 01背包转移
    }

    // 检查是否能取到答案上界
    if (sum <= k || sum <= n - k)
        return mxdep + 1;
    for (int i = 0; i <= sum; i++) {
        if (dp[i]) {
            if (i <= k && sum - i <= n - k) {
                return mxdep + 1;
            }
        }
    }

    // 不能取到上界，返回 d-1
    return mxdep;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        cout << solve<1>(n, k) << "\n";
    }
    return 0;
}

---

五、复杂度（最重要）

• 二进制拆分后物品数：$O(\sqrt{n})$
• bitset转移：$O\left(\dfrac{n}{\omega}\right)$ 每个物品
• 总复杂度：

$$\boldsymbol{O\left(\frac{n\sqrt{n}}{\omega}\right)} $$

$\omega=64$，$n=2\times10^5$ 轻松通过。

---

六、极简总结（可直接背）

1. 答案上界 = 叶子最小深度 $d$
2. 前 $d$ 层必须每层整体染色
3. 转化为 多重背包可行性问题
4. 二进制拆分 + bitset 优化背包
5. 合法 $\Rightarrow d$，不合法 $\Rightarrow d-1$

---