思路与算法

先使用结构等价：在每个非叶结点任意选一个儿子作为重儿子，得到若干重链。在此重链模型中，定义某结点的贡献为根到该点路径上最长的重链连续段长度；最大化这些贡献之和，与原题最大化各子树mex之和等价。这里的重儿子是待优化选择，不是按子树大小固定选择。该等价亦见NOI网站的本题分析。

完整状态W(u,M,L)表示当前到u的重链长度为L、此前各链最大长度为M时，u子树的最优贡献。令V=max(M,L)，有W(u,M,L)=V+ΣW(v,V,1)+max(0,max_v(W(v,M,L+1)-W(v,V,1)))：每个儿子默认开新链，最多选择一个儿子延续当前链。直接保存全部L很慢。

压缩为A[M][u]=W(u,M,1)，B[M+1][u]=W(u,M,M+1)。B由儿子状态直接转移。对A，当前链只有连续延长M条边后才可能首次超过历史M，因此枚举深度恰为dep[u]+M的后代v，把默认的A[M][v]换成B[M+1][v]。必须扣除u到v严格内部结点在基准ΣA中已经选过的最优增益，不能重复领取这些增益。

固定M，按深度从大到小处理。Euler序使子树成为区间。差分树状数组把每个已处理结点的增益加到其严格后代，查询v时得到路径上已计入的内部增益；在目标深度层建立线段树，维护B[M+1][v]-A[M][v]-已计内部增益，查询u子树内最大值并与0取大。先算完同深度所有A，再将这些增益更新至严格子树。最后根的当前链长为1，取1+ΣA[1][v]+max(0,max_v(B[2][v]-A[1][v]))。

正确性说明

本解采用本题公开分析给出的结构等价定理：原mex目标的最大值，等于在所有重儿子选择中，祖先路径最长连续重链段长度之和的最大值。这里比较的是最大总和，不声称两个模型中同一顶点的贡献逐点相同；链上的标签方向与路径长度方向可以相反。定理可参见NOI公开分析。下面证明在这个等价模型上的精确优化；小规模另直接枚举原mex定义，不依赖该变换来生成答案。

W递推枚举了u的全部重儿子选择：不延续时各儿子独立开新链，延续某一儿子时只替换该儿子的状态。因此完整递推正确。B的当前链已超过历史最大值，下一步或继续超过、或结束并把M+1作为新历史，正是其直接转移。

A在前M-1次延长期间，贡献仍为M。若从不超过M，可以取默认各子树A；若首次超过M，必在距离M的唯一后代v处发生，此后贡献由B[M+1][v]完整表示。基准A中沿这条路径严格内部结点原先的增益必须全部撤销，其他分支不变，所以差值正是B-A减去内部增益。深度倒序保证需要的后代状态已计算，差分树状数组的严格子树更新只累计路径内部增益，目标层区间最大值恰好枚举所有可选v。由M和深度的双重倒序归纳，压缩状态等于完整W，根公式得到最优值。

复杂度

设实际高度H≤m≤800。建树、Euler序与深度分组O(n)；A、B初始化空间及时间O(nH)。每个M处理各结点并查询或更新树状数组、深度层线段树，O(n log n)，合计O(nH log n)时间、O(nH+n)空间；深度层总长度为n。多组顺序释放。答案≤n²，可用int，n=8000时状态矩阵约51MB。

易错点

父亲编号小于儿子，输入编号从1计，内部转换成0计。使用实际高度H，星形即使m较大也不应分配无用深度层。树状数组只更新严格子树，不能包含自身；同深度增益须在该层查询结束后统一加入。延长重链时必须扣除路径上已有的gain，否则会把同一分支的最优增益重复计数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DepthTree {
    int base = 1;
    vector<int> tin, tree;
    void init(vector<int> ids, const vector<int> &in) {
        tin.clear();
        for (int v : ids)
            tin.push_back(in[v]);
        while (base < (int)ids.size())
            base *= 2;
        tree.assign(2 * base, 0);
    }
    void build(const vector<int> &ids, const vector<int> &delta) {
        fill(tree.begin(), tree.end(), 0);
        for (int i = 0; i < (int)ids.size(); i++)
            tree[base + i] = delta[ids[i]];
        for (int i = base - 1; i; i--)
            tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
    }
    int query(int l, int r) const {
        l = lower_bound(tin.begin(), tin.end(), l) - tin.begin();
        r = upper_bound(tin.begin(), tin.end(), r) - tin.begin();
        int ans = 0;
        for (l += base, r += base; l < r; l /= 2, r /= 2) {
            if (l & 1)
                ans = max(ans, tree[l++]);
            if (r & 1)
                ans = max(ans, tree[--r]);
        }
        return ans;
    }
};
struct Fenwick {
    int n;
    vector<int> a;
    Fenwick(int n) : n(n), a(n + 2) {
    }
    void add(int p, int v) {
        for (++p; p <= n + 1; p += p & -p)
            a[p] += v;
    }
    int point(int p) {
        int v = 0;
        for (++p; p; p -= p & -p)
            v += a[p];
        return v;
    }
    void strictSubtree(int l, int r, int v) {
        if (l + 1 <= r) {
            add(l + 1, v);
            add(r + 1, -v);
        }
    }
};
int solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<int> dep(n), par(n, -1);
    int H = 0;
    for (int v = 1; v < n; v++) {
        cin >> par[v];
        --par[v];
        g[par[v]].push_back(v);
        dep[v] = dep[par[v]] + 1;
        H = max(H, dep[v]);
    }
    vector<int> in(n), out(n), order;
    vector<int> st(1, 0);
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        in[u] = order.size();
        order.push_back(u);
        for (auto it = g[u].rbegin(); it != g[u].rend(); it++)
            st.push_back(*it);
    }
    vector<int> sz(n, 1);
    for (int i = n - 1; i > 0; i--)
        sz[par[order[i]]] += sz[order[i]];
    for (int u = 0; u < n; u++)
        out[u] = in[u] + sz[u] - 1;
    vector<vector<int>> ids(H + 1);
    for (int u : order)
        ids[dep[u]].push_back(u);
    vector<DepthTree> trees(H + 1);
    for (int d = 0; d <= H; d++)
        trees[d].init(ids[d], in);
    vector<vector<int>> A(H + 2, vector<int>(n)), B(H + 3, vector<int>(n));
    vector<int> delta(n);
    for (int M = H; M >= 1; M--) {
        for (int d = H; d >= M; d--)
            for (int u : ids[d]) {
                int val = M + 1, best = 0;
                for (int v : g[u]) {
                    val += A[M + 1][v];
                    best = max(best, B[M + 2][v] - A[M + 1][v]);
                }
                B[M + 1][u] = val + best;
            }
        Fenwick gains(n);
        vector<int> gain(n), adjusted(n);
        for (int d = H; d >= M; d--) {
            if (d + M <= H) {
                for (int v : ids[d + M])
                    adjusted[v] = delta[v] - gains.point(in[v]);
                trees[d + M].build(ids[d + M], adjusted);
            }
            for (int u : ids[d]) {
                int val = M;
                for (int v : g[u])
                    val += A[M][v];
                gain[u] = d + M <= H ? trees[d + M].query(in[u], out[u]) : 0;
                val += gain[u];
                A[M][u] = val;
                delta[u] = B[M + 1][u] - val;
            }
            for (int u : ids[d])
                if (gain[u])
                    gains.strictSubtree(in[u], out[u], gain[u]);
        }
    }
    int ans = 1, best = 0;
    for (int v : g[0]) {
        ans += A[1][v];
        best = max(best, B[2][v] - A[1][v]);
    }
    return ans + best;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        cout << solve() << '\n';
}