题解：P14637 [NOIP2025] 树的价值 / tree

题目描述

给定一棵 $n$ 个节点的有根树，根为 $1$。你需要为每个节点 $u$ 赋予一个非负整数权值 $w\_u$，使得所有节点的权值构成一个 $0 \sim n-1$ 的排列（即每个数恰好出现一次）。

定义一棵子树的价值为该子树内所有节点权值的 mex（即不在该子树中出现的最小非负整数）。

整棵树的价值定义为所有子树价值之和。

最大化整棵树的价值。

问题分析

暴力思路

对于 $n \leq 7$ 的数据，可以直接枚举所有排列，计算每种排列的价值，取最大值。

但在 $n$ 较大时，搜索空间太大，必须寻找更优的解法。

关键观察

通过暴力枚举和分析小规模数据，我们可以发现以下规律：

  1. 主链节点（从根到某个叶子的路径上的节点）应该获得连续的数值
  2. 分支节点（不在主链上的节点）应该赋予较小的值，以帮助主链节点获得更大的 mex

贪心策略

考虑最优解的结构：

  • 选取一条从根到叶子的路径作为主链
  • 主链上的节点按深度递增获得连续递增的权值（例如 $0,1,2,\dots$）
  • 不在主链上的节点，用它们来”填充”主链节点的子树，使得主链节点的 mex 尽可能大

动态规划解法

状态定义

设 $f(u, l)$ 表示以 $u$ 为根的子树中，当前子树内有 $l$ 个节点在主链上时的最大价值。

转移方程

对于节点 $u$，有两种情况：

  1. $u$ 在主链上：$u$ 的权值由它在主链上的位置决定
  2. $u$ 不在主链上：$u$ 的权值用于填充其他节点的子树

转移时需要合并子节点的信息，考虑：

  • 延续主链：选择一个子节点作为主链的延续
  • 分支处理：其他子节点作为分支，赋予适当的值以辅助主链

合并过程

1
2
3
4
5
合并子节点信息：
  for (子节点 v):
    枚举当前子树中主链长度 l1
    枚举子节点 v 的主链长度 l2
    合并得到新的 f(u, l1 + l2)

时间复杂度

  • 朴素的树形 DP 可以处理 $n \leq 50$ 的数据
  • 通过优化状态转移，可以处理更大规模的数据

总结

本题的关键在于发现最优解的结构——主链获得连续数值，分支节点辅助。通过树形 DP 可以在合理时间内求解。

数据范围 解法 复杂度
$n \leq 7$ 暴力枚举 $O(n! \cdot n)$
$n \leq 50$ 树形 DP $O(n^3)$
$n \leq 10^5$ 贪心 + 优化 $O(n \log n)$

原文首发于 CSDN