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

· · 题解

首先，我们可以发现对于这棵树整体，一定有一条链自下而上的一条总链，会放弃掉沿途一些链的自身贡献，来壮大这条总链。

所以，这棵树有两种点，一种是守本分，为所在这条链做出本身贡献，不忠于总链的点，另一种是为总链贡献的点。

但是我们发现这并不好统计，因为从上到下具有奇怪的不确定性。所以我们考虑其为上方的链所做的贡献。

一个点的贡献一定为一段区间，起始为这个点本身，终点为汇入总链之中被总链覆盖的位置。

所以，我们设 dp_{i,j,0/1}，表示第 i 个点，会做出 j 的贡献，零表示不是总链上的点，一表示是总链上的点，总的表示以 i 为根的子树的最大值。

那么，对于一个点，其儿子最多有一个点是总链上的。所以可以对其进行转移更新，那么 dp_{i,j,1} = \max(dp_{i,j,1}, dp_{son,j+1,1} + dp_{i,j,0} - dp_{son,j,0})。

我们可以先假定全不是总链上的点，在计算 i 的时候，将一个不是总链上的点变为总链上的点，取其最大值。

那么，就可以将其所带来的子树影响用 DFS 序的方式压在序列上，因为一个子树上的点在 DFS 序上同属一个区间，即连在一起的，所以可以对每一层开树状数组，来区间加和。

最终答案即为 dp_{1, 1, 1}。

一定要记得清空完！！！

时间复杂度：O(nm\log{n})。

下面是代码：

#include<bits/stdc++.h>
using namespace std;
int t, n, m, f[8005], deep[8005], dp[8005][805][2], in[8005], ou[8005], cnt, wrd[8005], tree[8005][805];
vector<int> v[8005];
int lowerbit(int x) {
    return x & (-x);
}
void change(int x, int y, int id) {
    for (; x <= n; x += lowerbit(x)) {
        tree[x][id] += y;
    }
}
int getsum(int x, int id) {
    int res = 0;
    for (; x; x -= lowerbit(x)) {
        res += tree[x][id];
    }
    return res;
}
void dfs(int u) {
    deep[u] = deep[f[u]] + 1;
    in[u] = ++cnt;
    wrd[cnt] = u;
    for (auto i : v[u]) {
        dfs(i);
    }
    ou[u] = cnt;
    for (int i = 1; i <= deep[u]; i ++) {
        dp[u][i][0] = i;
        dp[u][i][1] = i;
        for (auto j : v[u]) {
            dp[u][i][0] += dp[j][i][0];
        }
        // cerr << dp[u][i][0] << " " << u << " " << i << " $\n";
        for (auto j : v[u]) {
            dp[u][i][1] = max(dp[u][i][1], dp[j][i + 1][1] + dp[u][i][0] - dp[j][i][0]);
            // cerr << dp[u][i][1] << " " << u << " " << i << "\n";
            change(in[j], dp[u][i][0] - dp[j][i][0], i);
            change(ou[j] + 1, dp[j][i][0] - dp[u][i][0], i);
        }
    }
    for (int i = in[u] + 1; i <= ou[u]; i ++) {
        dp[u][deep[wrd[i]] - deep[u]][0] = max(dp[u][deep[wrd[i]] - deep[u]][0], getsum(i, deep[wrd[i]] - deep[u]) + dp[wrd[i]][deep[wrd[i]] - deep[u] + 1][1]);
        // cerr << dp[u][deep[wrd[i]] - deep[u]][0] << " " << deep[wrd[i]] << " " <<  u << "\n";
    }
}
signed main() {
    // freopen("tree1.in", "r", stdin);
    // freopen("tree.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t --) {
        cin >> n >> m;
        for (int i = 2; i <= n; i ++) {
            cin >> f[i];
            v[f[i]].push_back(i);
        }
        dfs(1);
        cout << dp[1][1][1] << "\n";
        for (int i = 1; i <= n; i ++) {
            v[i].clear();
        }
        memset(tree, 0, sizeof(tree));
        memset(dp, 0, sizeof(dp));
        cnt = 0;
    }
    return 0;
}