大逃杀

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

树形背包:把一条起点到终点的路线拆成最多两条开口的腿,三态 DP 合并儿子求带主路径的连通块最大收益。

OJ: roj

题目 ID: 1774

难度:提高+/省选-

标签:树形dp背包动态规划python

创建: 2026-10-08 01:53

更新: 2026-10-08 01:53

形式化题目

给定一棵 nn 个点的树,点 uu 有两个非负权值:资源值 wuw_u 和敌人耗时 tut_u; 边 e=(x,y)e=(x,y) 有权值 cec_e(通过耗时)。可以从任意点出发(空降不耗时), 在总耗时不超过 TT 的前提下沿边走,要求最大化收益。

到达点 uu 时必须支付 tut_u 一次(敌人只能被打一次,之后消失), 支付后若 wu>0w_u > 0 即可拿走 wuw_u(也可以不要);资源与敌人一旦处理就不再出现。 于是设实际访问过的点集为 S⊆{1,…,n}S \subseteq \{1,\dots,n\},SS 必须是一棵连通子树, 收益为 ∑u∈Swu\sum_{u \in S} w_u。设这次行动的路线是 SS 上的一条从起点到终点的行走序列 RR,则

cost(S,R)=∑u∈Stu  +  ∑e∈Rme⋅ce,me={1,e 在路线上只走一次(主路径),2,e 走了两次(进支路再原路返回). \text{cost}(S, R) = \sum_{u \in S} t_u \;+\; \sum_{e \in R} m_e \cdot c_e, \qquad m_e = \begin{cases} 1, & e \text{ 在路线上只走一次(主路径)},\\ 2, & e \text{ 走了两次(进支路再原路返回)}.\end{cases}

在 cost≤T\text{cost} \le T 的约束下求 max⁡∑u∈Swu\max \sum_{u\in S} w_u。

正解

思路

先看清路线的形状。 在一棵树上从起点走到终点,走过的每条边要么在"树干"上走一次, 要么在"支路"上为去而返走两次。把路线经过的所有边合并成子图,它是一棵子树 SS; 路线本身是一条从某点 ss 到某点 tt 的简单路径 PP(称主路径,s=ts = t 时退化成单点), SS 中不在 PP 上的边都恰好往返两次。写成公式:

cost(S)=min⁡P⊆S(∑u∈Stu+∑e∈Pce+2∑e∈S∖Pce)=∑u∈Stu+2 E(S)−diam⁡(S), \text{cost}(S) = \min_{P \subseteq S} \Big(\sum_{u \in S} t_u + \sum_{e \in P} c_e + 2\sum_{e \in S \setminus P} c_e\Big) = \sum_{u\in S} t_u + 2\,E(S) - \operatorname{diam}(S),

其中 E(S)=∑e∈SceE(S) = \sum_{e \in S} c_e,diam⁡(S)\operatorname{diam}(S) 是 SS 内最远两点的距离 (取 PP 为直径时取到最小值,因为每条边被"少走一次"的额度正好在路径上)。 这个恒等式是本题的一切:它把"枚举起点、枚举终点、枚举路线"三重自由度 压缩成"点集"一个自由度,且代价只依赖 SS 的三个可加量。

朴素做法。 枚举所有连通子树 SS(O(2n)O(2^n) 级别),再用树形 DP 算 diam⁡(S)\operatorname{diam}(S), 在 n⩽300n \leqslant 300 下完全不可行。哪怕只在 DFS 序上做"连通块背包", 也需要 O(2n)O(2^n) 的枚举,必须换思路。

树形背包:以“路线的最高点”为根。 任取 1 号点为根。麻烦之处在于:主路径的两个端点 可能落在根的两棵不同子树里,甚至一个在根的上方、一个在下方。因此改用一个固定的基准: 选定一个点 uu 作为主路径上深度最小的点,整条路线就是从 uu 往下伸出的若干条“腿”: 腿是从 uu 出发一路向下、不回头的一段路径;两条腿合起来构成主路径,其余分支都是往返。

一条路线只有两个端点,所以 uu 处最多有两条开口的腿,回到 uu 的支路都是封闭往返。 按"已伸出的腿数"分三种状态对每个点做 0/1 背包:

定义 dpk[u][j]dp_k[u][j] 为:在 uu 的子树内,uu 处已经伸出 kk 条开口的腿, 总耗时恰好为 jj 时能拿到的最大资源值(k=0,1,2k = 0,1,2,下标 jj 上取 max⁡\max)。初始时 uu 自己必须被打:dp0[u][tu]=dp1[u][tu]=dp2[u][tu]=wudp_0[u][t_u] = dp_1[u][t_u] = dp_2[u][t_u] = w_u。

合并儿子 vv(边权 cc)时,只需考虑 vv 那侧的子树以哪种形态接进来:

接法 边 (u,v)(u,v) 走的次数 腿数变化 vv 侧贡献
往返进去看看 2c2c +0+0 dp0[v]dp_0[v](vv 内部全是往返)
单程伸一条腿到 vv cc +1+1 dp1[v]dp_1[v](vv 内部已有一条腿)
往返,但 vv 内部自带两条腿 2c2c +2+2 dp2[v]dp_2[v](vv 内部自有主路径)

于是转移为

dp0[u][j]+=dp0[v][s],dp1[u][j]+=max⁡{dp1[v][s](j=k+c+s)dp0[v][s](j=k+2c+s), dp_0[u][j] \mathrel{+}= dp_0[v][s], \qquad dp_1[u][j] \mathrel{+}= \max\begin{cases} dp_1[v][s] & (j = k + c + s)\\ dp_0[v][s] & (j = k + 2c + s)\end{cases},
dp2[u][j]+=max⁡{dp2[v][s](j=k+2c+s)dp1[v][s](j=k+c+s)dp0[v][s](j=k+2c+s)其中 k 是合并前 u 的耗时. dp_2[u][j] \mathrel{+}= \max\begin{cases} dp_2[v][s] & (j = k + 2c + s)\\ dp_1[v][s] & (j = k + c + s)\\ dp_0[v][s] & (j = k + 2c + s) \end{cases}\quad \text{其中 } k \text{ 是合并前 } u \text{ 的耗时}.

合并一个儿子时必须用中转数组先把 uu 的旧状态誊出来, 否则同一个儿子会被"用两次"(dp2dp_2 是两条腿,同一条边不能被计入两条腿)。

为什么三种状态就够了、答案怎么取? 腿数只能从 0 涨到 2(路线两个端点), 所以 dp2dp_2 是终点;又因为下界是"恰好耗时",直接对所有点、所有耗时取 max⁡(dp0,dp1,dp2)\max(dp_0, dp_1, dp_2) 即可——多出来的时间不用完不影响收益, 而"恰好"语义只是把不可达状态设为 −∞-\infty,不会漏掉最优。空降起点与终点 可以是同一个点,对应 dp0dp_0 或单个点初始状态,已经被覆盖。 若 tu>Tt_u > T,点 uu 自己无法作为落脚点(空降或走到它都要付 tu>Tt_u > T), 但它子孙仍可以被空降直接到达,所以只跳过 uu 自身的初始状态,不等价于剪掉整棵子树。

n,T⩽300n, T \leqslant 300,每个点对每个儿子做 O(T2)O(T^2) 背包、每个点再乘 deg⁡(u)\deg(u), 总时间 O(n T2)=2.7×107O(n\,T^2)=2.7\times 10^7;空间 3nT3 n T,即 O(nT)O(nT)。

代码

C++ 版:

cpp
/**
 * 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 用可哈希的行数组原地合并):

python
#!/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()

复杂度

  • 时间:O(nT2)O(n T^2)。每个儿子 vv 并入父亲 uu 时枚举 kk(合并前 uu 的耗时)与 ss(留给 vv 子树的耗时),是 O(T2)O(T^2);树上每条边恰好贡献一次这样的合并, 共 n−1n-1 条边,所以总量 O(nT2)O(nT^2)。n,T=300n,T=300 时约 2.7×1072.7\times 10^7 次转移, 实测远快于 1000 ms 限时。
  • 空间:O(nT)O(nT) 的三张 DP 表(3×305×3013 \times 305 \times 301 个 long long,约 2.2 MB)加邻接数组,远小于 256 MB。

总结

  • 把"走法"换成"点集":路线的所有自由度最终收敛成 cost(S)=∑tu+2E(S)−diam⁡(S)\text{cost}(S) = \sum t_u + 2E(S) - \operatorname{diam}(S)—— 每条边额外走一次的代价有且只有直径上的那些边能省掉。
  • 按主路径的最高点分腿:以路线中深度最小的点为基准,其余部分就是最多两条 向下的开口腿 + 一堆封闭往返,于是"任意起终点"退化成腿数 0/1/2 三个状态。
  • 0/1 背包必须用旧状态起手:合并儿子时先誊写 uu 的旧行,才不会让同一个儿子 被重复计入(尤其 dp2dp_2 的两条腿)。
  • 恰好耗时 + 全局取 max:耗时非负意味着"少用时更自由",最后遍历所有点与 所有时间取最优,不需要额外枚举起点终点。
  • 打不过的点不必剪整棵子树:tu>Tt_u > T 时 uu 自己无法作为落脚点,但其子孙仍可被空降直接到达, 所以只跳过 uu 自己的初始化,照常递归求子树的 DP(答案对所有点取 max 时会用到它们)。