设 dp[u] 为以 u 为根能得到的最大二叉树高度，把最深孩子放到兄弟链最后，就有转移 dp[u]=儿子数+max(dp[child])。
OJ: luogu
题目 ID: P8744
难度:普及/提高-
标签:树形DP树动态规划递推
日期: 2026-06-21 03:28
题意
给一棵多叉树，允许任意安排每个结点孩子的顺序，再按左孩子右兄弟表示法转成二叉树。
要求求出：
- 所有可能转化结果中
- 二叉树的最大高度
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
int n;
vector<int> children[MAXN];
int brute_height(int u) {
if (children[u].empty()) {
return 0;
}
vector<int> perm = children[u];
sort(perm.begin(), perm.end());
int ans = 0;
do {
for (size_t i = 0; i < perm.size(); i++) {
// 从 u 走到第 i 个孩子，需要先走 1 条左边，再走 i 条右兄弟边。
ans = max(ans, 1 + (int)i + brute_height(perm[i]));
}
} while (next_permutation(perm.begin(), perm.end()));
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 这是一个小数据精确暴力：
// 枚举每个结点儿子的排列顺序，直接按左孩子右兄弟定义求最高高度。
cin >> n;
for (int i = 1; i <= n; i++) {
children[i].clear();
}
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
children[p].push_back(i);
}
cout << brute_height(1) << '\n';
return 0;
}brute.cpp 对每个结点枚举孩子排列，直接按定义求最大高度。
这个方法完全正确，但只能做很小的数据。
关键观察是：
如果结点 u 有 k 个孩子，那么某个孩子若排在第 i 个位置，它最终对高度的贡献是：
1 + i + dp[child]
其中：
1来自左孩子边i来自它前面那些右兄弟边
所以如果我们想让高度尽量大，显然应该把“子树最高”的那个孩子放到最后。
于是立刻得到转移：
- 叶子：
dp[u] = 0 - 非叶子：
dp[u] = 儿子数 + max(dp[child])
因为题目保证父亲编号小于儿子编号，所以我们甚至不用 DFS 排序，直接从 n 倒着算到 1 就行。
样例树可以画成这样：
graph G {
1 -- 2;
1 -- 3;
1 -- 4;
2 -- 5;
}
这里根 1 有 3 个孩子。
为了让高度最大，应该把“还带着一个孩子 5” 的结点 2 放在兄弟链最后。
这样它能多吃到最多的右兄弟边，所以最终答案是 4。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
int n;
vector<int> children[MAXN];
int parent_arr[MAXN];
int dp[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
children[i].clear();
parent_arr[i] = 0;
dp[i] = 0;
}
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
parent_arr[i] = p;
children[p].push_back(i);
}
// 由于保证父亲编号小于儿子编号，可以直接倒序做树形 DP。
for (int u = n; u >= 1; u--) {
int best_child = 0;
for (size_t i = 0; i < children[u].size(); i++) {
int v = children[u][i];
best_child = max(best_child, dp[v]);
}
if (children[u].empty()) {
dp[u] = 0;
} else {
// 把“收益最大”的儿子放到兄弟链的最后面，能多吃到最多的右兄弟边。
dp[u] = (int)children[u].size() + best_child;
}
}
cout << dp[1] << '\n';
return 0;
}复杂度
整棵树只需要线性扫描一次。
时间复杂度是
总结
这题最核心的一句话就是：
- 最深的那棵子树，应该放到最后一个兄弟位置
一旦看清这一点，整题就会化成一个非常短的树形 DP。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
