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

Caii · 2025-12-01 16:43:19 · 题解

约定：

对于一个节点 x，如果 x 取值对 x 的 {\rm mex} 有贡献，我们称 x 是一个红点。
对于一个节点 x，如果 x 取值对 x 的 {\rm mex} 没有贡献，我们称 x 是一个蓝点。

如上图所示：

红点 x 的贡献 = x 到根路径上连续红点段长度 + 红点段之后连续蓝点段长度。

但是，蓝点段贡献只能被一段红点所享有，例如中间图，点 7 和点 8 的路径上都有蓝点 3，此时点 3 的贡献只能被一段享有，因此 7 的贡献为 2，8 的贡献为 1。

由上面这一点，我们可以规定一个点最多只有一个红点儿子，因为多个红点儿子，必然由红点儿子贡献为 1，将其变成蓝点不会变差。
蓝点 x 的贡献 = x 祖先第一个红点的贡献

例如 5 的贡献为 2，因为 5 的祖先中第一个红点为 2，其贡献为 2。

设 f(x, k) 表示红点 x 贡献为 k 时，x 子树的最大贡献和；g(x, k) 表示蓝点 x 贡献为 k 时，x 子树的最大贡献和。

对于红点，每个点只有一个红点儿子，其他都是蓝点儿子，而根据蓝点贡献计算方式可知这些蓝点儿子的贡献与 x 是一样的。实际上通过这一点也可以说明如果 x 有儿子则必有红点儿子，因为红点儿子贡献为 x 贡献 +1。转移为：

f(x, k)=\max_{1\leq i\leq t}\left\{f(x_i, k+1)+\sum_{j\neq i}g(x_j, k)+k\right\}

对于蓝点 x，先考虑简单的情况：如果 x 子树中都是蓝点，则

g(x, k)\leftarrow k+\sum_{1\leq i\leq t}g(x_i, k)

如果 x 子树中存在红点，则会复杂一些，因为 x 子树中只有一段红点可以享有 x 这个蓝点段的贡献，我们要计算这个贡献，不妨设这个点为 v，则 DP 值为 x 子树中除子树 v 外所有点贡献之和最大值加上 v 的贡献。

如上图所示，这个图有很多性质：

如果 $v$ 的贡献大于 $k+1$，则可以将 $v$ 的父亲变成红点，其新的贡献为 $v$ 的贡献减去 $1$，大于 $k$，更优。因此 $v$ 的贡献不超过 $k+1$。如果 $v$ 的贡献小于 $k+1$，则将 $v$ 变成蓝点贡献不会变差。综上：$v$ 贡献为 $k+1$。实际上根据上面的分析 $v$ 的贡献为 $k$ 也是优的，但是存在例外情况，例如第一张图点 $7$ 的贡献只能为 $2$，不能为 $1$。
根据红点贡献计算方式，v 的贡献为 {\rm dep}(v)-{\rm dep}(x)+1，因此 k={\rm dep}(v)-{\rm dep}(x)。

综上，转移方程为

g(x, k)\leftarrow k+f(v, k+1)+\sum_{c在x到v路径上，是x到v路径上除v外某个点的儿子}g(c, k)

我们要维护后面的那个求和，可以使用数据结构，例如 DP 到 x 到 v 路径上一个点 y 时，设其有 r 个儿子 z_1, z_2, \cdots, z_r，我们对于 1\leq i\leq r，对 z_i 子树内所有点的 f(\cdot, k+1) 值加上 \sum_{j\neq i}g(z_j, k)，这样就能快速计算 DP 值了。需要区间加，单点查，可以使用树状数组。

最后答案为 f(1, 1)，时间复杂度为 O(nm\log n)。

#include <bits/stdc++.h>

const int N = 8000 + 7;
const int M = 800 + 7;

std::vector<int> e[N];
int bit[M][N], f[N][M], g[N][M], n, m;
int dfn[N], nfd[N], ed[N], cdfn, dep[N];

void add(int *bit, int x, int v) {
  while(x <= n) {
    bit[x] += v;
    x += x & -x;
  }
}

int ask(int *bit, int x) {
  int ret = 0;
  while(x) {
    ret += bit[x];
    x -= x & -x;
  }
  return ret;
}

void dfs(int x) {
  dfn[x] = ++cdfn;
  nfd[cdfn] = x;
  for(int v: e[x]) {
    dep[v] = dep[x] + 1;
    dfs(v);
  }
  ed[x] = cdfn;
  for(int i = 1; i <= dep[x]; ++i) {
    f[x][i] = g[x][i] = i;
    for(int v: e[x])
      g[x][i] += g[v][i];
    for(int v: e[x])
      f[x][i] = std::max(f[x][i], f[v][i + 1] + g[x][i] - g[v][i]);
    for(int v: e[x]) {
      add(bit[i], dfn[v], g[x][i] - g[v][i]);
      add(bit[i], ed[v] + 1, g[v][i] - g[x][i]);
    }
  }
  for(int j = dfn[x] + 1; j <= ed[x]; ++j) {
    int i = dep[nfd[j]] - dep[x] + 1;
    g[x][i - 1] = std::max(g[x][i - 1], ask(bit[i - 1], j) + f[nfd[j]][i]);
  }
}  

void solve() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; ++i)
    e[i].clear();
  for(int i = 2, x; i <= n; ++i) {
    scanf("%d", &x);
    e[x].push_back(i);
  }
  memset(bit, 0, sizeof bit);
  cdfn = 0;
  dep[1] = 1;
  dfs(1);
  printf("%d\n", f[1][1]);
}

int main() {

  freopen("tree.in", "r", stdin);
  freopen("tree.out", "w", stdout);

  int cases;
  scanf("%d", &cases);

  while(cases--)
    solve();

  return 0;
}