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

违规用户名720023 · 2025-12-05 17:46:42 · 题解

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

作者已严肃 AFO。

思路

首先有一个 O(n^3) 的 dp，设 dp_{i, j, k} 表示 i 号点子树的 \operatorname{mex} 为 j，有 k 个点的贡献还未产生的最大权值，转移没啥好说的，它和正解没有关系。我们的这个做法完全没有用题目给的一些深度的性质，跑的飞慢。

我们发现一个点的值对其子树的 \operatorname{mex} 可能但不一定产生贡献，所以如果这个点的数值对全子树 \operatorname{mex} 产生贡献那么将这个点叫做重要点，显然根是重要点比根不是重要点更优。

令一个点的贡献代表它对答案的改变量。特别的，当一个点孩子子树内同时有 [1,j] 和 [j + 1,k] 且这个点为 j 时这个点 \operatorname{mex} 增加到 k，我们认为数值是 [j,k] 的每一个点（相同数值只取一个）都对上面产生了 1，而不是在这个点产生 k - j + 1。

一个点的贡献情况如下：

如果这个点重要，那么它对上方重连续段每个点产生了一次贡献（因为上面每个点答案都因为它加一），它还可能对重连续段上方的一段轻（非重）连续段产生了贡献（因为这一段的答案也因为它加了一）如下图此时上面的那个点的 \operatorname{mex} 也是 1。注意每一个轻连续段只能产生一次贡献，因为一个轻点的子树 \operatorname{mex} 是它所有重后代的子树 \operatorname{mex} 的 \max。

如果这个点不重要，那么其贡献就是上方第一个重要的点的贡献，相当于钦定这个点为上方第一个重祖先产生贡献，显然这么做不影响答案。

显然可以钦定每个点只有最多一个重儿子。

发现一个点能够产生贡献的段是祖链上一段区间，于是对着这个 dp，设 dp_{i, j, 0/1} 表示 i 的子树，贡献的段长度为 j，是否是重要点的最大权值。

初值部分代码：

dp[p][i][0] = dp[p][i][1] = i;
for(int j = 0; j < a[p].size(); j++) dp[p][i][0] += dp[a[p][j]][i][0];

转移 dp[p][i][1] 是简单的，它的 \operatorname{mex} 一定从一个子树转移而来，这个子树的根一定是重要点，枚举取 \max 即可。

dp[p][i][0] 转移有两种情况，第一种是初值，即子树内不存在重要点。第二种是子树有重要点的情况，找到 dfn 最小的这种点，显然其上方和前面子树肯定没有其他重点，它会享有上面一坨轻点的贡献。它上方的轻点的贡献都是 dep[dy[i]] - dep[p] 所以转移方程为：

dp[p][dep[dy[i]] - dep[p]][0] = max(dp[p][dep[dy[i]] - dep[p]][0], dp[dy[i]][dep[dy[i]] - dep[p] + 1][1] + bits[dep[dy[i]] - dep[p]].fdsm(i));

其中 dp[dy[i]][dep[dy[i]] - dep[p] + 1][1] 是这个重点的答案，bits[dep[dy[i]] - dep[p]].fdsm(i) 是树状数组维护的轻链上轻子树的答案。维护方法见代码。

Code

#include <iostream>
#include <vector>
#include <cstring>
#define int long long
using namespace std;
int n, m;
struct BIT {
    int c[8010], sz;
    int lowbit(int x) { return x & -x; }
    void resiz(int siz) { for(int i = 0; i <= siz; i++) c[i] = 0; sz = siz; }
    void add(int p, int num) { for(int i = p; i <= sz; i += lowbit(i)) c[i] += num; }
    int fdsm(int p) {
        int res = 0;
        for(int i = p; i; i -= lowbit(i)) res += c[i];
        return res;
    }
}bits[810];
int fa[8010], dp[8010][810][2], tot, dy[8010];
vector<int> a[8010];
int dfn[8010], mxd[8010], dep[8010];
void dfs(int p) {
    dep[p] = dep[fa[p]] + 1;
    dfn[p] = ++tot;
    dy[tot] = p;
    for(int i = 0; i < a[p].size(); i++) dfs(a[p][i]);
    mxd[p] = tot;
    for(int i = 1; i <= dep[p]; i++) {
        dp[p][i][0] = dp[p][i][1] = i;
        for(int j = 0; j < a[p].size(); j++) dp[p][i][0] += dp[a[p][j]][i][0];
        for(int j = 0; j < a[p].size(); j++) { // 若自己是重点，那么一定有重儿子，钦定每个儿子为重儿子计算答案
            dp[p][i][1] = max(dp[p][i][1], dp[p][i][0] - dp[a[p][j]][i][0] + dp[a[p][j]][i + 1][1]);
            bits[i].add(dfn[a[p][j]], dp[p][i][0] - dp[a[p][j]][i][0]);
            bits[i].add(mxd[a[p][j]] + 1, dp[a[p][j]][i][0] - dp[p][i][0]); // 维护轻部分答案
        }
    }
    for(int i = dfn[p] + 1; i <= mxd[p]; i++) {
        dp[p][dep[dy[i]] - dep[p]][0] = max(dp[p][dep[dy[i]] - dep[p]][0], dp[dy[i]][dep[dy[i]] - dep[p] + 1][1] + bits[dep[dy[i]] - dep[p]].fdsm(i)); // 这里巧妙使用 bit，使得查询出来的部分恰好减去了 dp[dy[i]][dep[dy[i]] - dep[p]][0] 的部分
    }
}
signed main() {
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i = 0; i <= m; i++) bits[i].resiz(n);
        tot = 0;
        for(int i = 2; i <= n; i++) {
            cin >> fa[i];
            a[fa[i]].push_back(i);
        }
        dfs(1);
        cout << dp[1][1][1] << '\n';
        for(int i = 1; i <= n; i++) a[i].clear(), a[i].shrink_to_fit();
    }
    return 0;
}

后记

我也不知道为啥要说 n^3，反正大家都说了我也就放上来了。