一、题意回顾

给定以 $1$ 为根的有根树，共 $n$ 个节点； 每个节点填 $0/1$，要求恰好填 $k$ 个 $0$、$n-k$ 个 $1$。

• 节点 $u$ 的串：根到 $u$ 路径上点的标记拼接，记为 $\mathit{name}_u$；
• 叶子：无儿子的节点；
• 树的美观度：所有叶子串的最长公共子序列 LCS 长度； 求在合法染色方案下，美观度的最大值。

---

二、核心关键结论

1. 设所有叶子的深度最小值为：

$$d = \min_{u\text{ 是叶子}} \mathit{dep}[u]$$

每条叶子串长度等于自身深度，多串 LCS 的上界为最短串长度，因此：

$$\textbf{答案上界} = d$$

2. 若能构造方案使得所有叶子共享一段长度为 $d$ 的公共子序列 $\boldsymbol{\Rightarrow}$ 答案可取到 $d$； 若无法满足 $0/1$ 数量限制，则答案一定可以取到 $\boldsymbol{d-1}$。

3. 取到上界 $d$ 的充要条件： 对每一层深度 $1\sim d$，整层所有节点强制染同一种颜色； 深度 $>d$ 的节点可任意染色，用来补齐 $0/1$ 数量。

---

三、原理推导

1. 深度层分组

设：

• 根深度为 $\mathit{dep}=1$；
• $cnt[i]$：深度为 $i$ 的节点总个数。

要让所有叶子拥有长度为 $d$ 的公共 LCS： 必须让前 $d$ 层，每层颜色统一： 第 $1$ 层全同色、第 $2$ 层全同色……第 $d$ 层全同色。 这样所有根到叶子的前 $d$ 位结构完全一致，天然存在长度为 $d$ 的公共子序列。

2. 转化为 01 背包问题

前 $d$ 层每层只能整块选：全选 $0$ 或全选 $1$。

• 每层代价：该层节点总数 $cnt[i]$；
• 目标：从前 $d$ 层选出若干层染 $0$，设总个数为 $s$； 需要满足限制：

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

• $sum$：前 $d$ 层总节点数；
• 剩余节点（深度$>d$）可以自由填 $0/1$，一定能补全数量要求。

3. 取不到 $d$ 时的结论

若背包无解，无法让前 $d$ 层每层同色，则： 必然可以构造出答案为 $d-1$。 只放弃最深一层的统一染色，上层保持同色，一定满足数量限制。

---

四、算法流程

1. 建树，预处理每个节点深度 $\mathit{dep}$、统计每层大小 $cnt[]$；
2. 找出所有叶子，求出最小叶子深度 $d$；
3. 对前 $0\sim d$ 层做二进制背包 DP：
   • $dp[j]=1$ 表示：恰好选 $j$ 个节点染 $0$ 是可行的；
4. 检验是否存在合法 $s$：

$$s\le k,\ \ sum-s \le n-k$$

• 存在：答案为 $d$；
• 不存在：答案为 $d-1$。

---

五、DP 状态设计

• $dp$ 布尔数组，$dp[x]$ 表示选出若干完整层，恰好占用 $x$ 个 $0$ 名额是否可行；
• 初始：$dp[0]=1$；
• 转移（倒序 01 背包）：

$$dp[j + cnt[i]] \gets dp[j + cnt[i]] \mid dp[j]$$

• 遍历前 $d$ 所有层完成转移。

---

六、标程逐段解析

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

int solve() {
    int n, k;
    cin >> n >> k;
    // fa:父节点 dep:深度 noson:是否叶子
    vector<int> fa(n, -1), dep(n, 0);
    vector<int> noson(n, 1), cnt(n + 1, 0);
    cnt[0]++;

    // 读入父节点，预处理深度、层数计数、叶子标记
    for (int i = 1; i < n; i++) {
        cin >> fa[i];
        fa[i]--;            // 转为0下标
        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]);

    int sum = 0;
    vector<int> dp(n + 1, 0);
    dp[0] = 1;

    // 背包：前 mxdep 层，每层整块选
    for (int i = 0; i <= mxdep; i++) {
        for (int j = sum; j >= 0; j--)
            if (dp[j])
                dp[j + cnt[i]] = 1;
        sum += cnt[i];
    }

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

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

小注：代码使用 $0$ 下标节点，深度偏移导致最终输出写 mxdep+1，逻辑等价。

---

七、复杂度分析

• 背包层数最多 $n$，每层转移 $O(n)$；
• 总复杂度：

$$O(n^2)$$

完全满足简单版 $n\le 1000$ 的数据范围。

---

八、整体总结

1. 核心转化：$\textbf{LCS 最大值} \iff \textbf{叶子最小深度}$；
2. 约束转化：每层同色 $\rightarrow$ 多层分组背包；
3. 二元答案：背包合法取 $d$，不合法取 $d-1$；
4. 思维关键点：多层统一染色构造公共子序列，是本题贪心+DP 的核心。