把删点顺序转成树边定向，再做树形 DP，维护子树向根汇总权值与根向下可达点数的 Pareto 状态。
OJ: luogu
题目 ID: P9111
难度:提高+/省选-
标签:动态规划树形DP建模树
日期: 2026-06-21 11:27
题意
有 n 个 AI，通信关系是一棵树。
每个 AI 一开始存有一道难度为 d_i 的题。
每次选择一个当前还有题的 AI，把它里面的题出掉。出题前，它会把这道题发给所有相邻的、当前还没被清空的 AI：
- 如果对方还有题，就把两题难度相加
- 如果对方已经没题，就这次发送作废
要求选择一个出题顺序，使得最终一共出的 n 道题的难度和最大。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
const ll NEG_INF = -(1LL << 60);
int n;
ll d[15];
vector<int> g[15];
int permu[15];
int posi[15];
vector<int> out[15];
// 统计固定删点顺序下的总答案。
ll calc_one_order() {
for (int i = 1; i <= n; i++) {
posi[permu[i]] = i;
out[i].clear();
}
// 一条边一定从“更早被删的点”指向“更晚被删的点”。
for (int u = 1; u <= n; u++) {
for (int v : g[u]) {
if (u < v) {
if (posi[u] < posi[v]) {
out[u].push_back(v);
}
else {
out[v].push_back(u);
}
}
}
}
ll total = 0;
for (int s = 1; s <= n; s++) {
queue<int> q;
vector<int> vis(n + 1, 0);
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
total += d[s];
for (int v : out[u]) {
if (!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return total;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> d[i];
permu[i] = i;
}
for (int i = 2; i <= n; i++) {
int c;
cin >> c;
g[i].push_back(c);
g[c].push_back(i);
}
ll ans = NEG_INF;
sort(permu + 1, permu + n + 1);
do {
ans = max(ans, calc_one_order());
} while (next_permutation(permu + 1, permu + n + 1));
cout << ans << '\n';
return 0;
}暴力枚举删点顺序以后，整个过程其实就被完全确定了。
关键观察是：一条边两端谁先被删，谁后被删，会决定这条边上的题是往哪个方向传。
所以我们可以把每条树边看成一条有向边：
- 若
u比v先删，就连u -> v
这样整棵树就变成了一棵 DAG，而且答案只和这组边的定向有关，不再需要显式模拟“每一步删谁”。
对于一个点 s，它最终出的题难度，等于所有能沿着有向边从 s 走到的点的初始权值之和。
于是总答案变成：
- 对每个点
s，统计它能到达多少个点 - 把这些可达点的权值加总
接下来做树形 DP。
设我们只看 u 的子树，需要维护两类信息：
W：子树里有多少总权值，最终能汇总到uC：从u出发，沿着当前定向能到达多少个点
再设 F 为这棵子树内部已经确定的总答案。
为什么这三个量够用？
因为合并一个儿子 v 时，只有两种选择：
-
v -> u- 那么
v子树能汇到u的权值W_v，会对u当前能到达的C_u个点各贡献一次 - 新贡献是
W_v * C_u
- 那么
-
u -> v- 那么
u当前能汇到的权值W_u，会对v子树里u能继续走到的C_v个点各贡献一次 - 新贡献是
W_u * C_v
- 那么
所以转移非常直接：
DP 转移方程：树上定向合并
合并儿子 v 时，当前状态为 (W_u,C_u,F_u)，儿子状态为 (W_v,C_v,F_v)。
只有两种边方向：
v -> u：(W_u + W_v, C_u, F_u + F_v + W_v * C_u)u -> v：(W_u, C_u + C_v, F_u + F_v + W_u * C_v)
这里会出现很多状态，但对于固定的 C，如果两个状态满足：
- 一个状态的
W更大 - 同时
F也更大
那较差的那个以后不可能翻盘，可以直接删掉。
因此代码里对每个 C 只保留 (W, F) 的 Pareto 前沿。
这样就能在 n = 400 的范围内通过。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG_INF = -(1LL << 60);
const int MAXN = 405;
int n;
ll d[MAXN];
vector<int> g[MAXN];
vector<int> child[MAXN];
vector<int> order_nodes;
// states[u][c] = 若干个 (W, F)
// c : 在子树 u 中，从 u 出发沿定向边能到达的点数
// W : 能通过反向链路汇总到 u 的总权值
// F : 这棵子树内部的总答案
vector<vector<pair<ll, ll> > > states[MAXN];
void dfs_build(int u, int fa) {
order_nodes.push_back(u);
for (int v : g[u]) {
if (v == fa) {
continue;
}
child[u].push_back(v);
dfs_build(v, u);
}
}
// 固定同一个 c 时，保留 (W, F) 的 Pareto 前沿。
// 如果存在另一个状态同时满足 W 更大且 F 更大，那么当前状态以后不可能更优。
vector<pair<ll, ll> > prune_same_c(vector<pair<ll, ll> > vec) {
sort(vec.begin(), vec.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b) {
if (a.first != b.first) {
return a.first > b.first;
}
return a.second > b.second;
});
vector<pair<ll, ll> > res;
ll best_f = NEG_INF;
int i = 0;
while (i < (int) vec.size()) {
int j = i;
ll cur_w = vec[i].first;
ll best_this_w = NEG_INF;
while (j < (int) vec.size() && vec[j].first == cur_w) {
best_this_w = max(best_this_w, vec[j].second);
j++;
}
if (best_this_w > best_f) {
res.push_back(make_pair(cur_w, best_this_w));
best_f = best_this_w;
}
i = j;
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> d[i];
}
for (int i = 2; i <= n; i++) {
int c;
cin >> c;
g[i].push_back(c);
g[c].push_back(i);
}
dfs_build(1, 0);
for (int idx = (int) order_nodes.size() - 1; idx >= 0; idx--) {
int u = order_nodes[idx];
// dp[c]：当前已经合并完若干个儿子后，能形成的 (W, F) 前沿。
vector<vector<pair<ll, ll> > > dp(2);
dp[1].push_back(make_pair(d[u], d[u]));
for (int v : child[u]) {
vector<vector<pair<ll, ll> > > ndp((int) dp.size() + (int) states[v].size());
for (int cu = 1; cu < (int) dp.size(); cu++) {
if (dp[cu].empty()) {
continue;
}
for (pair<ll, ll> now : dp[cu]) {
ll wu = now.first;
ll fu = now.second;
for (int cv = 1; cv < (int) states[v].size(); cv++) {
if (states[v][cv].empty()) {
continue;
}
for (pair<ll, ll> son : states[v][cv]) {
ll wv = son.first;
ll fv = son.second;
// 方案 1：v -> u
// 子树 v 的权值能汇到 u，u 的可达点数不变。
ndp[cu].push_back(make_pair(
wu + wv,
fu + fv + wv * cu
));
// 方案 2：u -> v
// u 能继续走进 v 子树，u 的可达点数增加 cv。
ndp[cu + cv].push_back(make_pair(
wu,
fu + fv + wu * cv
));
}
}
}
}
for (int c = 1; c < (int) ndp.size(); c++) {
if (!ndp[c].empty()) {
ndp[c] = prune_same_c(ndp[c]);
}
}
dp.swap(ndp);
}
states[u].swap(dp);
}
ll ans = NEG_INF;
for (int c = 1; c < (int) states[1].size(); c++) {
for (pair<ll, ll> st : states[1][c]) {
ans = max(ans, st.second);
}
}
cout << ans << '\n';
return 0;
}复杂度
设每个点保留下来的 Pareto 状态数为 S。
转移复杂度大致是
空间复杂度约为
总结
这题最关键的建模，不是“出题过程怎么模拟”，而是把它改写成：
- 每条边按照删点先后关系定向
一旦这样看，整题就会变成一棵树上的定向 DP。
状态里真正重要的是：
- 能往上汇多少权值
- 能往下覆盖多少点
抓住这两个量以后，合并儿子就是很自然的两种方向分类讨论。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
