题解：P14637 [NOIP2025] 树的价值 / tree（官方数据）

· · 题解

容易设置 dp_{i, j, k} 表示 i 子树中的 \text{mex} 为 j，且有 k 个神秘节点以后再钦定数字的最大权值。可以使用类似树形背包的方式转移，j 维度取 \max，k 维度加和，再多一个额外转移 f_{i, j + 1, k - 1} \larr f_{i, j, k} 即可，复杂度 O(n^3)，证明类似树形背包。

我们发现这个三维状态很伤啊，完全不好转移，因此需要再考虑一下后两个维度是在怎么贡献。

观察后知道具体加上多少贡献只跟 j 有关系，这个 k 的作用仅仅就是燃烧自己让 j 变大。因此我们会下意识地认为一个 k（即一个点）的贡献是一段从根开始的祖先链，到哪个节点取决于 k 什么时候减一。

然而这个想法不完全对。这是因为 j 是取 \max，可能 k 的一个贡献网上跳着跳着就被其他有更大 j 的兄弟节点夺舍了。因此正确的贡献是一段从自己到根的祖先链上的一段区间。

这个 \max 很烦人，我们不妨放宽条件，钦定一个点的 j 可以任意取一个儿子的 j，这样不合法者不优，不影响答案。这样一来取 \max 的过程变成了“给每个节点分配一个重儿子”。原问题被重新拆解如下：

现在有一棵树，你需要对这棵树进行链剖分。规定一个点的贡献是其到根节点的祖先链的一个区间的点数，且要求区间内的点处于同一条链上。求权值最大的剖分方式对应的权值。

容易设出 \text{DP} 方程如下：dp_{i, j, k} 表示 i 节点处于当前链的第 k 个节点，且往上跳可以找出最大合法区间长度为 j 的最大权值。转移是容易的，复杂度为 O(nm^2)。

继续用数据结构优化。有转移的部分只有 dp_{i, j, 1} 和 dp_{i, j, j}，不妨记作 f_{i, j} 和 g_{i, j}。我们考虑用 \text{DS} 维护 f, g 之间的填表法转移。

对于 f_{i, j}，如果 i 子树的树高不大于 j，那么无论如何剖分，其总贡献一定是 siz_i \times j。否则枚举 i 的 j 级儿子 p（规定自己是第 0 级儿子，以此类推），可能的转移是 g_{p, j + 1} 加上 i \to p 链上每个节点在链外的 f 值之和。我们用 \text{dfs} 序技巧，树状数组即可维护毛毛虫单修区查。

对于 g_{i, j}，一定是取其中一个儿子 p 的 g_{p, j + 1} 和其他儿子的 f_{x, j}。

如果看不懂的话代码里有注释，感觉还是挺清楚的。

/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 8010, M = 810, INF = 1e9;
int T, n, m, fa[N]; vector < int > tr[N];
// 考虑 dp[i][j][k] 表示子树 i 中 mex 为 j，有 k 个神秘节点没有用的最大方案
// 神秘节点的本质是让一段祖先的贡献加 1，这个一段与 max 的划分有关
// 考虑人为划分这个 max，错误的划分不优
// 则改设 dp[i][j][k] 表示子树 i 中处在当前链的第 k 个节点，祖先最长段为 j
// 复杂度 O(nm^2) 
// 这个状态的转移仅仅发生在 dp[i][j][1] 或者 dp[i][j][j]
// 考虑简化状态，设置 f[i][j] = dp[i][j][1], g[i][j] = dp[i][j][j]
// 并在 f 和 g 之间相互转移，数据结构维护 

int dfn[N], df_sign, siz[N];
inline void init(int pos, int prt)
{
    dfn[pos] = ++df_sign, siz[pos] = 1;
    for(int to : tr[pos])
    {
        if(to == prt) continue;
        init(to, pos), siz[pos] += siz[to];
    }
}
struct BIT
{
    int c[N];
    inline void reset() {memset(c, 0, sizeof(c));}
    inline void add(int pos, int num)
    {for(int i = pos; i <= n; i += lowbit(i)) c[i] += num;}
    inline void insert(int l, int r, int num)
    {add(l, num), add(r + 1, -num);}
    inline int query(int pos)
    {
        int res = 0;
        for(int i = pos; i; i -= lowbit(i)) res += c[i];
        return res;
    }
};
struct Tree
{
    BIT bit[2];
    inline void reset() {for(int i = 0; i <= 1; ++i) bit[i].reset();}
    inline void add_point(int pt, int num)
    {
        bit[0].insert(dfn[pt], dfn[pt] + siz[pt] - 1, num);
        if(fa[pt]) bit[1].insert(dfn[fa[pt]], dfn[fa[pt]] + siz[fa[pt]] - 1, num);
    }
    inline int query_chain(int type, int x, int y)
    {
        return bit[type].query(dfn[x]) - bit[type].query(dfn[y]);
    }
}; Tree tree[M];
// 上面使用 dfn 序和树状数组构建了 m 个数据结构
// 每个数据结构可以做单点加法，链上求和以及毛毛虫（足长 1）求和
// 0 代表链，1 代表毛毛虫 
// 该数据结构是为了 f, g 的转移 

int f[N][M], g[N][M], h[N], dep[N];
vector < int > son[N][M];
inline void treedp(int pos, int prt)
{
    h[pos] = 1; // h 表示 pos 子树的高度 
    dep[pos] = dep[prt] + 1;
    son[pos][0].push_back(pos); // son[i][j] 存储距离 i 为 j 的儿子 
    for(int to : tr[pos])
    {
        treedp(to, pos);
        h[pos] = max(h[pos], h[to] + 1);
        for(int j = 0; j <= h[to]; ++j)
            for(int x : son[to][j])
                son[pos][j + 1].push_back(x);
    }
    for(int to : tr[pos])
        for(int i = 1; i <= dep[pos]; ++i)
            tree[i].add_point(to, f[to][i]);

    // 填表法 
    for(int i = 1; i <= dep[pos]; ++i)
    {
        // 转移 f[pos][i] 
        f[pos][i] = siz[pos] * i;
        for(int to : son[pos][i])
        {
            int current = g[to][i + 1];
            current += tree[i].query_chain(1, fa[to], 0);
            current -= tree[i].query_chain(0, to, 0);
            // 上面都没有更新，第二个参数传 0 减小常数 
            f[pos][i] = max(f[pos][i], current + i * i);
        }
    }
    for(int i = 1; i <= dep[pos]; ++i)
    {
        // 转移 g[pos][i] 
        int delta = -INF;
        if(tr[pos].empty()) delta = 0;
        for(int to : tr[pos])
        {
            g[pos][i] += f[to][i];
            delta = max(delta, g[to][i + 1] - f[to][i]);
        }
        g[pos][i] += i;
        g[pos][i] += delta;
    }
}
inline void sol()
{
    memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));
    cin >> n >> m; ++m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= h[i]; ++j)
            son[i][j].clear();
    for(int i = 0; i <= m; ++i) tree[i].reset();
    for(int i = 1; i <= n; ++i) tr[i].clear();
    for(int i = 2; i <= n; ++i) cin >> fa[i], tr[fa[i]].push_back(i);
    df_sign = 0; init(1, 0);
    treedp(1, 0);
    cout << f[1][1] << '\n';
}

int main()
{
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while(T--) sol();
    return 0;
}
/*
1
5 2
1 1 2 2
*/