1. 题意整理
给你一棵树，每个点 有一个权值 。
你可以选择一些边，使得任意两条被选中的边不能共用端点，也就是说这些边组成一个匹配。
规则是：
- 没有被匹配边覆盖到的点，自己承担自己的代价
- 如果一条边 被选中，那么这两个点合起来只算
目标是让总代价最小。
2. 这类题为什么适合树形 DP
因为图是一棵树，边之间没有环。
这意味着当我们以某个点为根后，每个儿子子树之间是互相独立的。
只要我们知道“当前节点和父亲之间是什么关系”，就可以把每个子树单独算出来，再组合起来。
3. 状态设计
我们把树根设为 。
定义两个状态：
表示：
- 没有和父亲配对
- 可以选择：
- 自己单独承担代价
- 或者和某一个儿子配对
也就是说， 这一层是“自由”的。
表示：
- 已经和父亲配对了
- 因此 不能再和任何儿子配对
这里要注意：
与父亲配对这一条边的代价，不在这个状态里算。
这个代价会在父亲决定选这条边的时候一起算掉。
4. 先看 taken[u] 怎么求
如果 已经和父亲配对了，那么 自己不能再去配对儿子。
所以每个儿子 都只能处于 free[v] 状态。
因此：
这里的 是 的所有儿子。
这一步非常自然：
父亲把 “占用了”，于是 的子树只能继续独立处理。
5. 再看 free[u] 怎么求
free[u] 有两种情况。
情况一： 不和任何儿子配对
那 就自己承担代价 ，每个儿子各自处理：
情况二： 和某个儿子 配对
这时候：
- 边 的代价是
- 不能再和自己的父亲配对，所以 必须进入
taken[v] - 其他儿子仍然是
free状态
所以代价是：
把公共部分提出来，就得到：
6. 合并公式
所以：
其中 遍历 的每个儿子。
7. 为什么这样是对的？
因为树上的每条边只连接父子。
当我们确定了：
- 是否和父亲配对
- 是否和某一个儿子配对
以后，其他子树就互不影响了。
所以最优解一定可以拆成各个儿子子树的最优解之和，再加上当前这一层的选择成本。
这正是树形 DP 的核心思想。
8. 如何高效计算
如果直接对每个儿子都重新求一遍和，会重复计算很多次。
我们先算：
那么：
taken[u] = sumFree- 如果 不和儿子配对，答案是
- 如果 和儿子 配对，答案是
这样每个点只扫一遍儿子，总复杂度就是 。
9. 复杂度分析
每条边只会被处理常数次，所以总复杂度为：
题目里 ，这个复杂度是完全可以通过的。
10. 参考代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
vector<ll> a;
vector<vector<int>> g;
vector<ll> free_dp, taken_dp;
vector<int> parent_node, order_nodes;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
g.assign(n + 1, {});
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
parent_node.assign(n + 1, 0);
order_nodes.clear();
order_nodes.reserve(n);
stack<int> st;
st.push(1);
parent_node[1] = -1;
while (!st.empty()) {
int u = st.top();
st.pop();
order_nodes.push_back(u);
for (int v : g[u]) {
if (v == parent_node[u]) {
continue;
}
parent_node[v] = u;
st.push(v);
}
}
free_dp.assign(n + 1, 0);
taken_dp.assign(n + 1, 0);
for (int idx = n - 1; idx >= 0; --idx) {
int u = order_nodes[idx];
ll sumFree = 0;
for (int v : g[u]) {
if (v == parent_node[u]) {
continue;
}
sumFree += free_dp[v];
}
taken_dp[u] = sumFree;
ll best = a[u] + sumFree;
for (int v : g[u]) {
if (v == parent_node[u]) {
continue;
}
ll cand = max(a[u], a[v]) + taken_dp[v] + (sumFree - free_dp[v]);
best = min(best, cand);
}
free_dp[u] = best;
}
cout << free_dp[1] << '\n';
return 0;
}
暂无评论