[NOIP2025] 树的价值

GitHub 跳转原题关系图返回列表

按 mex 基础层从大到小做树形 DP，并用长链剖分维护同深度的最优传递链。

OJ: luogu

题目 ID: P14637

难度:省选/NOI-

标签:树形结构树形DP长链剖分mex

日期: 2026-06-22 20:07

题意

给定一棵以 1 为根的有根树。需要给每个节点设置一个非负整数权值。

对节点 i，设 S_i 为它子树内所有节点权值构成的集合。树的价值为：

text

1sum mex(S_i)

要求在所有赋值方案中最大化这个价值。题目保证树高不超过 m。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;

int n, m;
vector<int> sons[MAXN];
int value_a[MAXN];
int best_answer;

void collect_values(int u, set<int> &values) {
    values.insert(value_a[u]);
    for (int i = 0; i < (int)sons[u].size(); i++) {
        collect_values(sons[u][i], values);
    }
}

int calc_mex_for_node(int u) {
    set<int> values;
    collect_values(u, values);
    int mex = 0;
    while (values.count(mex)) {
        mex++;
    }
    return mex;
}

void dfs_assign(int pos) {
    if (pos > n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += calc_mex_for_node(i);
        }
        best_answer = max(best_answer, sum);
        return;
    }

    for (int x = 0; x <= n; x++) {
        value_a[pos] = x;
        dfs_assign(pos + 1);
    }
}

void solve_case() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        sons[i].clear();
    }

    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        sons[p].push_back(i);
    }

    best_answer = 0;
    dfs_assign(1);
    cout << best_answer << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

暴力枚举每个节点的权值，再计算每个子树的 mex。它能帮助理解题意，但复杂度是指数级。

mex 的关键是连续性：如果一个子树的 mex 至少为 x，那么这个子树里必须同时出现 0,1,...,x-1。因此最优赋值可以理解为在树上安排一些连续值，让尽可能多的祖先子树获得更大的 mex。

正解按一个基础层 UM 从大到小做 DP。固定 UM 时，可以先把每个节点的贡献看作基础值，再考虑能否沿一条向下链继续把 mex 抬高。

代码中维护这些量：

f[u]：当前 UM 下，子树 u 的最优价值；
g[u][0]：当前 UM 下，从 u 开始继续传递连续值的最优值；
g[u][1]：上一层 UM+1 的传递结果；
best_same_depth[u][d]：在 u 的子树中，相对深度为 d 的最好传递链候选。

如果从节点 u 继续往某个儿子 v 传递，那么其他儿子就只贡献它们当前 f 的最优值。也就是说，每次传递只会选择一个主儿子继续往下，其余子树提供独立贡献。

为了快速合并同深度的候选，代码使用长链剖分：

预处理每个节点的最长向下链长度和重儿子；
重儿子复用父节点的深度数组；
轻儿子的深度信息再逐项合并到父节点数组中。

这样每一轮 UM 的 DFS 合并总量是 $O(n)$ ，外层有 $O(m)$ 轮。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140#include <bits/stdc++.h>
using namespace std;

const int MAXN = 8005;

int n, m;
vector<int> sons[MAXN];
int siz[MAXN], height_len[MAXN], heavy_son[MAXN];

int f[MAXN];          // 固定当前 UM 时，f[u] 表示子树 u 的最优值
int g[MAXN][2];       // g[u][0] 是当前 UM，g[u][1] 是 UM+1
int outside_sum[MAXN];
int delta[MAXN];
int pool[MAXN];
int pool_len;
int *best_same_depth[MAXN];
int current_um;

void update_max(int &x, int y) {
    if (y > x) {
        x = y;
    }
}

void dfs_prepare(int u) {
    siz[u] = 1;
    height_len[u] = 1;
    heavy_son[u] = 0;

    for (int i = 0; i < (int)sons[u].size(); i++) {
        int v = sons[u][i];
        dfs_prepare(v);
        siz[u] += siz[v];
        if (height_len[v] + 1 > height_len[u]) {
            height_len[u] = height_len[v] + 1;
            heavy_son[u] = v;
        }
    }
}

void dfs_dp(int u) {
    int child_f_sum = 0;

    if (best_same_depth[u] == nullptr) {
        best_same_depth[u] = pool + pool_len;
        pool_len += height_len[u];
    }

    if (heavy_son[u] != 0) {
        best_same_depth[heavy_son[u]] = best_same_depth[u] + 1;
    }

    f[u] = current_um * siz[u];
    g[u][0] = current_um * siz[u];

    for (int i = 0; i < (int)sons[u].size(); i++) {
        int v = sons[u][i];
        dfs_dp(v);
        child_f_sum += f[v];
    }

    for (int i = 0; i < (int)sons[u].size(); i++) {
        int v = sons[u][i];
        outside_sum[v] = child_f_sum - f[v];
        update_max(g[u][0], g[v][1] + current_um + outside_sum[v]);
    }

    if (heavy_son[u] != 0) {
        int hv = heavy_son[u];
        delta[u] = delta[hv] + outside_sum[hv];

        for (int i = 0; i < (int)sons[u].size(); i++) {
            int v = sons[u][i];
            if (v == hv) {
                continue;
            }
            for (int d = 1; d <= height_len[v]; d++) {
                int val = best_same_depth[v][d] + outside_sum[v] + delta[v] - delta[u];
                update_max(best_same_depth[u][d + 1], val);
            }
        }
    }

    best_same_depth[u][1] = g[u][0] - delta[u];
    if (height_len[u] >= current_um) {
        int val = best_same_depth[u][current_um] + delta[u] + current_um * (current_um - 1);
        update_max(f[u], val);
    }
}

void solve_case() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        sons[i].clear();
    }

    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        sons[p].push_back(i);
    }

    dfs_prepare(1);

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

    for (current_um = m + 1; current_um >= 1; current_um--) {
        pool_len = 0;
        for (int i = 0; i <= n + 2; i++) {
            pool[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            best_same_depth[i] = nullptr;
            delta[i] = 0;
            swap(g[i][0], g[i][1]);
        }

        dfs_dp(1);
    }

    cout << g[1][0] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve_case();
    }

    return 0;
}

复杂度

外层枚举 UM，最多 m+1 轮。每轮通过长链剖分完成一次 $O(n)$ 的树形 DP。

总时间复杂度为：

text

1O(nm)

空间复杂度为 $O(n)$ 。

总结

本题不是直接给每个节点算 mex，而是反过来考虑“要让 mex 达到某一层，需要子树里提供哪些连续值”。

固定基础层 UM 后，树形 DP 只需要决定哪条儿子链继续传递，其他子树取当前最优贡献。长链剖分负责把“同深度的最优链候选”高效合并起来。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P14637 [NOIP2025] 树的价值

题目描述

给定一棵 $n$ 个结点的有根树，其中结点 1 为根，结点 $i$ ( $2 \le i \le n$ ) 的父亲结点为结点 $p_i$ 。

对于 $1 \le i \le n$ ，定义结点 $i$ 的深度 $d_i$ 为结点 1 到结点 $i$ 的简单路径的边数，也就是说， $d_1 = 0$ ， $d_i = d_{p_i} + 1$ ( $2 \le i \le n$ )。定义有根树的高度 $h$ 为所有结点的深度的最大值，即 $h = \max_{i=1}^{n} d_i$ 。

给定高度的上界 $m$ 。在本题中，给定的有根树的高度不超过 $m$ 。

你需要给每个结点设置一个非负整数作为它的权值。对于 $1 \le i \le n$ ，若结点 $i$ 的权值为 $a_i$ ，令 $S_i$ 表示结点 $i$ 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为 $\sum_{i=1}^{n} \mathrm{mex}(S_i)$ ，其中 $\mathrm{mex}(S)$ 表示不在集合 $S$ 中的最小非负整数。例如，在下图中，若设置 $a_1 = 3$ ， $a_2 = 2$ ， $a_3 = a_4 = 0$ ， $a_5 = 1$ ，则 $S_1 = \{0,1,2,3\}$ ， $S_2 = \{0,1,2\}$ ， $S_3 = \{0\}$ ， $S_4 = \{0\}$ ， $S_5 = \{1\}$ ，树的价值为 $4 + 3 + 1 + 1 + 0 = 9$ 。

:::align{center} :::

你需要求出，在所有权值设置方案中，树的价值的最大值。

输入格式

本题包含多组测试数据。

输入的第一行包含一个正整数 $t$ ，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

第一行包含两个正整数 $n, m$ ，分别表示结点数量与高度的上界。
第二行包含 $n - 1$ 个正整数 $p_2, p_3, \ldots, p_n$ ，分别表示每个结点的父亲结点。

输出格式

对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。

输入输出样例 #1

输入 #1

text

1
2
3
4
52
5 2
1 1 2 2
7 2
1 1 2 2 2 3

输出 #1

text

1
29
13

说明/提示

【样例 1 解释】

该样例共包含两组测试数据。

对于第一组测试数据，可以设置 $a_1 = 3$ ， $a_2 = 2$ ， $a_3 = a_4 = 0$ ， $a_5 = 1$ ，则树的价值为 $4 + 3 + 1 + 1 + 0 = 9$ 。

对于第二组测试数据，可以设置 $a_1 = 4$ ， $a_2 = 3$ ， $a_4 = 2$ ， $a_3 = a_6 = 1$ ， $a_5 = a_7 = 0$ ，则树的价值为 $5 + 4 + 2 + 0 + 1 + 0 + 1 = 13$ 。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

该样例满足测试点 $3,4$ 的约束条件。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

该样例满足测试点 $7,8$ 的约束条件。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

该样例满足测试点 $13,14$ 的约束条件。

【样例 5】

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。

该样例满足测试点 $18,19$ 的约束条件。

【数据范围】

对于所有测试数据，均有：

$1 \le t \le 5$ ；
$2 \le n \le 8,000$ ， $1 \le m \le \min(n - 1, 800)$ ；
对于所有 $2 \le i \le n$ ，均有 $1 \le p_i \le i - 1$ ；
给定的有根树的高度不超过 $m$ 。

::cute-table{tuack}

测试点编号	$n \le$	$m \le$
$1,2$	$7$	$n-1$
$3,4$	$13$	^
$5,6$	$18$	^
$7,8$	$40$	^
$9,10$	$120$	^
$11,12$	$360$	^
$13,14$	$4{,}000$	$2$
$15\sim 17$	^	$10$
$18,19$	^	$50$
$20\sim 25$	$8{,}000$	$800$