树形背包:把一条起点到终点的路线拆成最多两条开口的腿,三态 DP 合并儿子求带主路径的连通块最大收益。
OJ: roj
题目 ID: 1774
难度:提高+/省选-
标签:树形dp背包动态规划python
创建: 2026-10-08 01:53
更新: 2026-10-08 01:53
形式化题目
给定一棵
到达点
在
正解
思路
先看清路线的形状。 在一棵树上从起点走到终点,走过的每条边要么在"树干"上走一次,
要么在"支路"上为去而返走两次。把路线经过的所有边合并成子图,它是一棵子树
其中
朴素做法。 枚举所有连通子树
树形背包:以“路线的最高点”为根。 任取 1 号点为根。麻烦之处在于:主路径的两个端点
可能落在根的两棵不同子树里,甚至一个在根的上方、一个在下方。因此改用一个固定的基准:
选定一个点
一条路线只有两个端点,所以
定义
合并儿子
| 接法 | 边 |
腿数变化 | |
|---|---|---|---|
| 往返进去看看 | |||
| 单程伸一条腿到 |
|||
| 往返,但 |
于是转移为
合并一个儿子时必须用中转数组先把
为什么三种状态就够了、答案怎么取? 腿数只能从 0 涨到 2(路线两个端点),
所以
代码
C++ 版:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 01:45
* update_at: 2026-10-08 01:53
*/
// main.cpp:一本通 1774《大逃杀》——树形背包(树上"带主路径"的连通块)。
//
// 题意:地图是一棵树,点 u 有资源 w[u](>=0,到达即可拿走)和敌人耗时 t[u](>=0,到达必须支付)。
// 可以从任意点空降,总时间 T,结束时武力值 = 走过的点的资源值之和(每种资源只拿一次)。
// 走过的点构成一棵连通子树 S,走路方式是一条从起点到终点的路线:路线上的边(主路径)走一次,
// 其余边为了去再回来必须走两次。所以总耗时 = Σ_{u∈S} t[u] + Σ_{e∈主路径} c[e] + 2·Σ_{e∈S\主路径} c[e]。
// 在耗时 <= T 的约束下最大化 Σ w。
//
// 算法:把"路线"拆成以最高点 u 为根的若干条腿(腿 = 从 u 往下走进去、不回来的一段)。
// 一条路线最多只有两个端点,故 u 处最多有 2 条开口的腿,其余分支都是"往返"。
// dp0[u][j]:腿数 0,从 u 出发走遍子树内一部分再回到 u,恰好耗时 j 的最大资源值;
// dp1[u][j]:腿数 1,从 u 出发,终点在子树内任意点,恰好耗时 j;
// dp2[u][j]:腿数 2,起点终点都在子树内、路线经过 u,恰好耗时 j。
// 合并儿子 v(边权 c)时是 0/1 背包,v 只有三种接法:
// 往返:耗时多 2c,腿数 +0,收益 dp0[v][...];
// 单程:耗时多 c,腿数 +1,收益 dp1[v][...];
// 往返但两条腿都在 v 内部:耗时多 2c,腿数 +2,收益 dp2[v][...]。
// 因为走路总耗时非负、耗时越少越自由,所以"恰好 j"的语义不会漏解:最后对所有点、所有 j 取 max。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 305; // n <= 300,多开一点
const ll NEG = -(1LL << 50); // 负无穷:表示该 (点, 耗时) 状态不可达
int n, T; // 点数、总时间
ll weight[MAXN]; // weight[u]:点 u 的资源值 w[u]
ll fight_time[MAXN]; // fight_time[u]:点 u 的杀敌耗时 t[u]
// dp0/dp1/dp2 的定义见文件头注释,第二维是"恰好耗时",值为该耗时下的最大资源值
ll dp0[MAXN][MAXN];
ll dp1[MAXN][MAXN];
ll dp2[MAXN][MAXN];
ll buf0[MAXN], buf1[MAXN], buf2[MAXN]; // 合并一个儿子时的中转数组,避免读到本轮刚写进 dp[u] 的值
struct Edge {
int to; // 边指向的点
int next; // 链式前向星的下一条边
ll cost; // 通过这条边的时间 c
};
Edge edge[MAXN * 2]; // 双向边,共 2(n-1) 条
int head[MAXN], edge_cnt;
// 加一条有向边 u -> v,权值 cost
void add_edge(int u, int v, ll cost) {
edge_cnt++;
edge[edge_cnt].to = v;
edge[edge_cnt].cost = cost;
edge[edge_cnt].next = head[u];
head[u] = edge_cnt;
}
// 树上背包:处理以 u 为根的子树(以 1 号为根,parent 是父节点)
void dfs(int u, int parent) {
// 注意:不能因为 u 自己打不过就剪掉整棵子树——u 的子孙仍然可以空降到达。
// 所以只在 u 自己可达时填初始状态,子树照常递归。
if (fight_time[u] <= T) {
dp0[u][fight_time[u]] = weight[u]; // 只待在 u 一个点上:三种腿数都成立
dp1[u][fight_time[u]] = weight[u];
dp2[u][fight_time[u]] = weight[u];
}
for (int e = head[u]; e; e = edge[e].next) {
int v = edge[e].to;
ll c = edge[e].cost;
if (v == parent) continue;
dfs(v, u);
// 把 u 现有的状态誊进 buf:本轮只从旧状态出发,保证 v 不会被同一个儿子用两次
for (int j = 0; j <= T; j++) {
buf0[j] = dp0[u][j];
buf1[j] = dp1[u][j];
buf2[j] = dp2[u][j];
}
for (int k = fight_time[u]; k <= T; k++) { // k:进 v 之前已经花掉的时间
ll a0 = dp0[u][k], a1 = dp1[u][k], a2 = dp2[u][k];
if (a0 <= NEG / 2 && a1 <= NEG / 2 && a2 <= NEG / 2) continue; // 该耗时不可达
// 接法一:单程进 v(腿数 +1),耗时 k + c + shen
for (int shen = 0; k + c + shen <= T; shen++) {
if (dp1[v][shen] <= NEG / 2) continue;
int j = k + c + shen;
buf1[j] = max(buf1[j], a0 + dp1[v][shen]); // 原先 0 条腿 -> 1 条
buf2[j] = max(buf2[j], a1 + dp1[v][shen]); // 原先 1 条腿 -> 2 条
}
// 接法二/三:往返进 v(边 (u,v) 走两次),耗时 k + 2c + shen
for (int shen = 0; k + 2 * c + shen <= T; shen++) {
int j = k + 2 * c + shen;
if (dp0[v][shen] > NEG / 2) { // v 内部自己往返:腿数不变
buf0[j] = max(buf0[j], a0 + dp0[v][shen]);
buf1[j] = max(buf1[j], a1 + dp0[v][shen]);
buf2[j] = max(buf2[j], a2 + dp0[v][shen]);
}
if (dp2[v][shen] > NEG / 2) // v 内部有两条腿:腿数 +2,只能从 0 条腿的状态接
buf2[j] = max(buf2[j], a0 + dp2[v][shen]);
}
}
for (int j = 0; j <= T; j++) { // 把合并结果写回 u
dp0[u][j] = buf0[j];
dp1[u][j] = buf1[j];
dp2[u][j] = buf2[j];
}
}
}
int main() {
scanf("%d %d", &n, &T);
for (int i = 1; i <= n; i++) scanf("%lld", &weight[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &fight_time[i]);
for (int i = 1; i <= n - 1; i++) {
int a, b;
ll c;
scanf("%d %d %lld", &a, &b, &c);
add_edge(a, b, c);
add_edge(b, a, c);
}
for (int u = 1; u <= n; u++)
for (int j = 0; j <= T; j++) dp0[u][j] = dp1[u][j] = dp2[u][j] = NEG;
dfs(1, 0);
ll ans = 0; // 一个点都去不了时武力值就是 0
for (int u = 1; u <= n; u++)
for (int j = 0; j <= T; j++) {
ans = max(ans, dp0[u][j]);
ans = max(ans, dp1[u][j]);
ans = max(ans, dp2[u][j]);
}
printf("%lld\n", ans);
return 0;
}Python 版(同一算法,三态 DP 用可哈希的行数组原地合并):
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 01:53
# update_at: 2026-10-08 01:53
import sys
UNREACHABLE = -1 # 资源值恒 >= 0,所以只要 -1 表示"这个耗时到不了",不需要更大的负无穷
type Row = list[int] # 一个点的 dp 行:下标 = 恰好耗时,值 = 该耗时下的最大资源值
type Son = tuple[Row, Row, Row] # 一个点的三种腿数状态:(往返, 单腿, 双腿)
type Adj = list[list[tuple[int, int]]] # adj[u] = [(相邻点, 边耗时), ...]
def attach(src: Son, son: Son, edge: int, base: int, limit: int) -> None:
"""把儿子子树并入 u,src 的三行原地更新;src 与 son 都是 (往返, 单腿, 双腿) 三元组。
边 (u,v) 走一次的两种接法:v 的"单腿"接成 u 的单腿 / 双腿(路径从 u 继续往 v 的下方走)。
边 (u,v) 走两次的三种接法:"往返"不改变腿数;"双腿"只在 u 还没伸腿时能接(u 自己成了绕路的端点外)。
"""
old_ret, old_end, old_mid = src[0][:], src[1][:], src[2][:]
son_ret, son_end, son_mid = son
# 只踩儿子子树里真正可达的耗时,叶子点只有 1 个可达耗时,能把星形图的合并压成 O(T)
reach = [s for s in range(limit - edge + 1)
if son_ret[s] >= 0 or son_end[s] >= 0 or son_mid[s] >= 0]
ret, end, mid = src
for k in range(base, limit - edge + 1): # k:接 v 之前 u 已经花掉的时间
a0, a1, a2 = old_ret[k], old_end[k], old_mid[k]
if a0 < 0 and a1 < 0 and a2 < 0: # 这个耗时在 u 处不可达
continue
room = limit - k - edge # 留给 v 子树的绝对上限
for s in reach:
if s > room: # reach 递增,后面的 s 更放不下
break
j = k + edge + s # 边 (u,v) 只走一次
one = son_end[s]
if one >= 0: # 路径经 (u,v) 进子树,u 这头多伸出一条腿
cand = a0 + one
if cand > end[j]:
end[j] = cand
cand = a1 + one
if cand > mid[j]:
mid[j] = cand
if s + edge > room: # 边 (u,v) 再走一次放不下
continue
j2 = j + edge # 往返去 v 子树
back = son_ret[s]
if back >= 0: # v 内部全是往返,u 的腿数不变
cand = a0 + back
if cand > ret[j2]:
ret[j2] = cand
cand = a1 + back
if cand > end[j2]:
end[j2] = cand
cand = a2 + back
if cand > mid[j2]:
mid[j2] = cand
both = son_mid[s]
if both >= 0: # v 内部自带整条主路径,u 只是绕过去看一眼
cand = a0 + both
if cand > mid[j2]:
mid[j2] = cand
def build_dp(n: int, limit: int, weight: Row, fight: Row, adj: Adj, parent: Row, order: list[int]) -> tuple[list[Row], list[Row], list[Row]]:
"""自叶向根做三态树形背包,返回 (往返, 单腿, 双腿) 三张 dp 表。"""
dp_ret: list[Row] = [[UNREACHABLE] * (limit + 1) for _ in range(n + 1)]
dp_end: list[Row] = [[UNREACHABLE] * (limit + 1) for _ in range(n + 1)]
dp_mid: list[Row] = [[UNREACHABLE] * (limit + 1) for _ in range(n + 1)]
for u in reversed(order): # 逆序保证轮到 u 时儿子的 dp 行都已算好
if fight[u] > limit: # u 自己打不过;子树由各自的 dp 行负责,答案会另行取到
continue
dp_ret[u][fight[u]] = dp_end[u][fight[u]] = dp_mid[u][fight[u]] = weight[u]
for v, c in adj[u]:
if v == parent[u]:
continue
attach((dp_ret[u], dp_end[u], dp_mid[u]),
(dp_ret[v], dp_end[v], dp_mid[v]), c, fight[u], limit)
return dp_ret, dp_end, dp_mid
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, limit = next(data), next(data)
weight = [0] + [next(data) for _ in range(n)] # weight[u]:点 u 的资源值 w_u
fight = [0] + [next(data) for _ in range(n)] # fight[u]:点 u 的杀敌耗时 t_u
adj: Adj = [[] for _ in range(n + 1)]
edge_count = n - 1 # 树上边数,题目保证输入恰好这么多条
for _ in range(edge_count):
a, b, c = next(data), next(data), next(data)
adj[a].append((b, c))
adj[b].append((a, c))
# 迭代求 dfs 序(父先于子),逆序处理就是自叶向根。
parent = [0] * (n + 1)
order: list[int] = []
stack = [1]
while stack:
u = stack.pop()
order.append(u)
for v, _ in adj[u]:
if v != parent[u]:
parent[v] = u
stack.append(v)
ret_rows, end_rows, mid_rows = build_dp(n, limit, weight, fight, adj, parent, order)
best = max(max(row) for table in (ret_rows, end_rows, mid_rows) for row in table)
print(max(best, 0)) # 一个点都进不去时武力值就是 0
if __name__ == "__main__":
solve()复杂度
- 时间:
。每个儿子 并入父亲 时枚举 (合并前 的耗时)与 (留给 子树的耗时),是 ;树上每条边恰好贡献一次这样的合并, 共 条边,所以总量 。 时约 次转移, 实测远快于 1000 ms 限时。 - 空间:
的三张 DP 表( 个 long long,约 2.2 MB)加邻接数组,远小于 256 MB。
总结
- 把"走法"换成"点集":路线的所有自由度最终收敛成
—— 每条边额外走一次的代价有且只有直径上的那些边能省掉。 - 按主路径的最高点分腿:以路线中深度最小的点为基准,其余部分就是最多两条 向下的开口腿 + 一堆封闭往返,于是"任意起终点"退化成腿数 0/1/2 三个状态。
- 0/1 背包必须用旧状态起手:合并儿子时先誊写
的旧行,才不会让同一个儿子 被重复计入(尤其 的两条腿)。 - 恰好耗时 + 全局取 max:耗时非负意味着"少用时更自由",最后遍历所有点与 所有时间取最优,不需要额外枚举起点终点。
- 打不过的点不必剪整棵子树:
时 自己无法作为落脚点,但其子孙仍可被空降直接到达, 所以只跳过 自己的初始化,照常递归求子树的 DP(答案对所有点取 max 时会用到它们)。