让程序按答案出生的顺序工作

市政厅要在周日开一场没有观众的展览。

展品藏在一栋旧楼里。楼里有走廊，有房间，有房间里的小房间。

每件展品都要花时间搬出来，走廊还收一笔来回通行费。

实习生负责排工。他拿着总表，从大厅开始逐格询问：左边房间准备好了吗，右边房间准备好了吗，上一层还缺哪一栏。

房间里的工人已经算过一遍。实习生仍然一次次敲门，把同一张表拆成许多小问题。

馆长看了十分钟，拿走总表。他把开门顺序改成：先让最里面的房间交货，再让走廊收货，最后大厅签字。

第二天，展览按时开门。没有观众，程序倒是终于看懂了这栋楼。

简化题面

┌─ [P1270] 访问美术馆
├─ 平台: 洛谷
├─ 题意: 给定一棵展馆树和参观时间预算，求最多能收集的画作数量。
├─ 输入: 根树的递归描述；节点表示走廊或展室，展室带有画作数量。
├─ 输出: 在总时间限制内最多收集的画作数。
├─ 数据范围: 节点数与时间预算有限，时间上限决定状态规模。
├─ 关键限制: 进入子树和返回走廊消耗时间，左右子树预算需要分配。
└─ 完整题面: https://www.luogu.com.cn/problem/P1270

先别急着追问大厅

定义 dp[x][t]：给节点 x 的子树 t 秒，最多收集多少幅画。

叶子展室先扣掉进入和返回走廊的时间，再按剩余时间计算能拿到的画。内部节点把预算分给左右子树，枚举分配点后合并两张表。

for (int t = 0; t <= T; ++t) {
    dp[x][t] = dp[left][t];
    for (int k = 0; k <= t; ++k)
        dp[x][t] = max(dp[x][t], dp[left][k] + dp[right][t-k]);
}

转移式本身很早就能写出来。慢点出在访问顺序。

第一版把递归函数写成 dfs(x,t)。父节点每问一个预算，就重新走一遍左右子树，再从记忆化表里取答案。

公式没有变，重复访问堆成了墙。

楼梯给了拓扑顺序

题目输入采用递归描述。读到一个内部节点，后面紧跟左子树，再跟右子树。

这份输入顺序已经把依赖写出来：孩子先完成，父亲再合并。程序不用带着预算参数到处敲门，可以在每个节点读完后一次性填表。

void build(int x) {
    read_node(x);
    if (is_leaf(x)) {
        fill_leaf(dp[x]);
        return;
    }
    build(left[x]);
    build(right[x]);
    merge_table(dp[x], dp[left[x]], dp[right[x]]);
}

递归仍然存在。它只负责安排依赖顺序，不再负责携带每个预算的询问。

这就是树上背包和普通记忆化搜索的分水岭之一：父状态需要孩子整张表时，先把孩子整张表算完，通常比逐个预算访问更干净。

up[x] 让表提前收工

每个节点有一个上界 up[x]。超过“取完这棵子树全部画作所需的时间”以后，答案不会继续增加。

for (int t = 0; t <= up[x]; ++t) {
    // 只计算仍可能改变答案的预算
}

up[x] 收缩状态数量。build 固定计算时机。

一个让表变小，一个让同一张表只填一次。

旧测试脚本记录了 287 组通过和约 0.02 秒的最慢样例。脚本没有标准答案，随机树最多 25 个节点。

这些数字只能说明程序在那批输入上运行顺利，不能替代转移证明。

先问答案依赖谁

很多 TLE 看起来像公式太慢。继续改公式之前，可以检查：

1. 当前状态要读取哪些子状态？
2. 这些子状态何时全部就绪？
3. 父状态是在等待整张表，还是只等一个格子？
4. 输入顺序能否直接提供一条依赖顺序？
5. 哪些预算超过上界以后不会再改变答案？

如果父状态需要孩子的整张表，逐格询问通常会制造重复劳动。让答案按依赖顺序出生，缓存才真正有用。

馆长关掉大厅的总表。最里面的房间先交货，走廊随后盖章，最后才轮到大厅。

没有观众的展览照常结束。门票打印机只吐出一行：0.02s。

发布信息草案

• 标题：让程序按答案出生的顺序工作
• 摘要：树上背包的状态依赖应直接决定计算顺序，子树整表先完成，父节点再合并。
• 标签：树上背包、区间 DP、依赖顺序、记忆化、性能优化