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

tiger2005 · 2025-12-03 13:48:49 · 题解

提供一个时间复杂度 \mathcal{O} (n m)，空间复杂度 \mathcal{O} (n) 的做法。

:::info[本文使用的记号]

• :::

定义树上一个结点的子树 \operatorname{mex} 为这个结点的价值，而整棵树的价值就是所有结点的价值之和。

首先可以注意到，对于一个结点，如果其价值为 k，那么对于子树内所有大于 k 的点权，在当前结点决策是没有用处的，那么可以选择置空，留给祖先决策。下面称这样的结点为“垫脚石”。

考虑最优化价值的策略，对于一个结点而言，必然是从其某个子结点已有的子树 \operatorname{mex} 结构开始，不断利用垫脚石提升自身的价值。

:::info[一个例子]{open} 假设根结点包含了三个子结点，对应的价值分别为 3, 6, 5，而垫脚石分别有 1, 2, 3 个。那么在仅考虑根结点决策的前提下，最优的做法是：在子树已经存在 [0, 5] 内所有点权的基础上，将 6 个垫脚石和自身分别设置为 [6, 12] 范围内两两不同的整数，这样就能把根结点的价值调整至 13。

注意到如下事实：

• 垫脚石实际上不一定要全部用完，可以进一步留给祖先使用；
• 所有结点在最开始的时候都是垫脚石，只不过其可以选择在自身使用，也可以选择在其祖先使用。
• 上述决策是只针对根结点进行的。实际上，可以选择将第二棵子树的两个垫脚石分别设置为 6 和 7，从而将这棵子树本身的价值提升到 8。 :::

通过这个性质足以设计出如下做法：

:::success[\mathcal{O} (n^3) 的做法]{open} 设 f(i, j, k) 表示考虑结点 i，其价值为 j，并且包含 k 个垫脚石，对应的子树价值和的最大值。不难通过树形动态规划做到 \mathcal{O} (n^4) 或者 \mathcal{O} (n^3)。 :::

进一步的观察可以发现，对于一个非叶子结点，会选择恰好一个子结点，并根据其已有的价值，将合适数量的垫脚石设置为合适的值。称每个结点选择的子结点和自身形成的边为传递边，那么每个非叶子结点都恰好往下连接了一条传递边，这就自然形成了树的剖分结构（一些经典的剖分结构为重链剖分和长链剖分）。这里需要明确，在传递边的系统下，一个结点的价值等于从传递边传递上来的价值，加上在这个结点使用的垫脚石数量。（可以通过上面的例子辅助思考）

之前的做法是尝试根据每个结点子树的情况动态决策出每个结点选择的传递边，不过这一做法较难扩展。考虑将思路反过来，首先确定传递边形成的剖分结构，随后在剖分结构上计算最优的点权填写方案。对于树上的结点，根据前面指出的事实，它们一开始都是垫脚石。当某个祖先结点选择了一个垫脚石并进行利用后，这个垫脚石的贡献会从这个祖先结点开始，顺着传递边向上走。

:::info[另一个例子]{open}

考虑如上树结构，其中红边表示传递边，而蓝边表示非传递边。对 12 号结点而言，如果在 10 号结点被利用，此时的贡献会从 10 号结点开始，不断传递到 9 号结点、8 号结点和 7 号结点，共产生四次贡献；如果在 3 号结点被利用，则会产生三次贡献。不难发现，在其他祖先上产生的贡献都不会超过 4，因此对于 12 号结点而言，其产生的最大贡献就是 4。

通过这个例子可以确定每个结点的最大贡献：考虑从这个结点到根结点的链，链上最长的传递链的长度（结点个数）就是这个结点的最大贡献。 :::

从这个例子可以发现：只需要在动态规划的转移方程维护到根结点链上的最长传递链的长度，即可独立计算出每个结点的贡献，相加后就是剖分下的最大价值。我们就得到了如下做法：

:::success[\mathcal{O} (n m^2) 的做法]{open} 设 f(i, j, k) 表示考虑结点 i，其到根结点路径上最长传递链长度为 j，而当前所在的传递链长度为 k，对应的子树价值和的最大值。转移时选择一个子结点延续传递链即可，可以做到 \mathcal{O} (n m^2) 转移。 :::

上述做法还是不够快。考虑到上述状态的参数空间为 [1, n] \times [1, m] \times [1, m]，不妨尝试利用某些手段，将状态拆分为两个参数空间为 [1, n] \times [1, m] 的状态，在两个状态之间转移，实现同样的功能。

为了将最长传递链参数和当前传递链参数分离，需要进行钦定，最终能够设计出如下状态：

考虑如何转移。g(i, j) 的转移是自然的，考虑选择一个子结点延续当前链，其他的子结点恰好对应 f(i, j) 的情况，可以得到:

• 默认转移 g(i, j) \leftarrow j \times \text{sz}(i)，表示子树内传递边没有任何作用；
• 对每一个子结点 v \in \text{sons}(i)，有转移 g(i, j) \leftarrow j + g(v, j + 1) + \sum_{\substack{w \in \text{sons}(i)\\ w \neq v}} f(w, j)

  这里的 j 项代表 i 本身的贡献。

接下来考虑 f(i, j) 的转移。子树内传递边没有作用对应的贡献就是 j \times \text{sz}(i)，而为了让新的链产生作用，则需要让新链的长度不小于 j。注意到 g(i, j) 拥有延长最长链的作用，因此只需要选择一个长度恰好为 j 的链，并从对应的 g(\cdot, j) 转移过来即可。链上所有结点的贡献都等于 j，而链上所有结点的链外分支对应的也恰好是 f(\cdot, j) 的情况。可以得到：

• 默认转移 f(i, j) \leftarrow j \times \text{sz}(i)，表示子树内传递边没有任何作用；

• 对每一个与 i 的距离恰好为 j - 1 的后代 v，有转移

  f(i, j) \leftarrow j (j - 1) + g(v, j) + \sum_{\substack{w \in \text{path}(i, v) \\ w \neq i}} h(w, j)

  这里的 j (j - 1) 项代表 i 本身的贡献，而 h(w) 表示的是其父结点的链外分支贡献和，可以写作：

  h(i, j) = \sum_{\substack{v \in \text{sons}(\text{fa}(i)) \\ v \neq i}} f(v, j)

对每个结点枚举其所有后代的时间复杂度是 \mathcal{O} (n m)（注意到一个结点只有最多 m 个祖先结点），而对于求和项，可以为每个 j 启用一个数据结构，通过支持子树加和单点查询计算每个结点 v 对应的求和项值。这个做法最终可以实现 \mathcal{O} (n m \log n) 的时间复杂度和 \mathcal{O} (n m) 的空间复杂度。

这个做法实际上已经足够我们通过这题了，不过为了得到更快且空间占用更小的做法，还需要做出一些努力。

首先可以注意到，f(i, j) 和 g(i, j) 只会通过 f(i, j)、g(i, j) 和 g(i, j + 1) 转移，因此可以在转移外层按照降序枚举变量 x，并将这一变量作为参数的第二维使用。此时只需要维护 \hat f(i) = f(i, x)、\hat g(i) = g(i, x) 和 \hat g'(i) = g(i, x + 1)，从而将空间占用降低至 \mathcal{O} (n)。

在固定 x 之后，考虑到目前的算法瓶颈为计算如下式子：

将大括号上方的权值视为 \hat s(v)，那么目标就是对结点 i 子树内同一层的所有结点 v 计算 \hat s(v) 的最大值。不妨假设 S(i, j) 表示对结点 i，其所有距离恰好为 j - 1 的后代 v 对应的 \hat s(v) 最大值，可以发现如下转移：

• 对每一个子结点 v \in \text{sons}(i) ，有转移 S(i, j + 1) \leftarrow S(v, j) + \hat h(v)；
• 最终的转移方程转化为 \hat f(i) \leftarrow x (x - 1) + S(i, x)。

注意到 S(i, j) 的第二维实际上不超过子树高度，并且第二条转移方程满足子树信息复用的形式，自然想到使用长链剖分优化上述转移。对于第二条转移方程中 \hat h(v) 部分，可以使用全局偏移数组维护，避免在复用的同时枚举所有元素。

这样就能在 \mathcal{O} (n) 的时间复杂度内完成 \hat f(i) 和 \hat g(i) 的计算，最终的时间复杂度就是 \mathcal{O} (n m)。

:::success[最终的代码]

int n, m;
int fa[8010], dep[8010];
vector<int> sons[8010];

int siz[8010], hgt[8010], hv[8010];
void dfs1(int x) {
  siz[x] = 1;
  hgt[x] = 1;
  hv[x] = 0;
  for (auto v : sons[x]) {
    dfs1(v), siz[x] += siz[v];
    if (ckmax(hgt[x], hgt[v] + 1))
      hv[x] = v;
  }
}

int f[8010], g[8010][2], h[8010];
int *sh[8010], pool[8010], len, delta[8010];
int UM;

void dfs2(int x) {
  int tmp = 0;
  if (sh[x] == nullptr) {
    sh[x] = pool + len;
    len += hgt[x];
  }
  if (hv[x])
    sh[hv[x]] = sh[x] + 1;

  f[x] = g[x][0] = UM * siz[x];
  for (auto v : sons[x])
    dfs2(v), tmp += f[v];
  for (auto v : sons[x]) {
    h[v] = tmp - f[v];
    ckmax(g[x][0], g[v][1] + UM + h[v]); 
  }

  if (hv[x]) {
    delta[x] = delta[hv[x]] + h[hv[x]];
    for (auto v : sons[x]) if (v != hv[x])
      for (int i = 1; i <= hgt[v]; i ++)
        ckmax(sh[x][i + 1], sh[v][i] + h[v] + delta[v] - delta[x]);
  }
  sh[x][1] = g[x][0] - delta[x];
  if (hgt[x] >= UM)
    ckmax(f[x], sh[x][UM] + delta[x] + UM * (UM - 1));
}

int main() {
  multiCase() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
      sons[i].clear();
    for (int i = 2; i <= n; i ++) {
      cin >> fa[i];
      sons[fa[i]].push_back(i);
      dep[i] = dep[fa[i]] + 1;
    }

    dfs1(1);
    for (int i = 1; i <= n; i ++)
      f[i] = g[i][0] = (m + 2) * siz[i];

    for (UM = m + 1; UM >= 1; UM --) {
      len = 0;
      for (int i = 1; i <= n; i ++)
        pool[i] = 0, sh[i] = nullptr, delta[i] = 0,
        swap(g[i][0], g[i][1]);
      dfs2(1);
    }

    printf("%d\n", g[1][0]);
  }
  return 0;
}

:::