GESP 题解库 / 7 级题解 / [GESP202412 七级] 燃烧 · 第 11 / 24 题
GESP202412 七级 · P11378 · 中等

树上的燃烧扩散

选一个结点引燃,火只从燃烧点扩散到权值严格更小的相邻点,求最多能烧掉多少结点。

📊
n ≤ 10⁵
结点数量
🔢
aᵢ ≤ 10⁶
点权范围
⚡
O(n log n)
时间复杂度
🎯
按权值升序递推 R[v]
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一棵包含 n 个结点的树,结点 i 的权值为 aᵢ。他可以选择一个结点引燃;每个燃烧的结点会把火扩散到它的相邻结点中权值严格小于自身的那些结点,直到不再有新结点被引燃。

问:合理选择初始结点时,最多可以燃烧多少个结点?

💡
人话翻译:火只能"下坡"走,而且必须严格下坡(权值变小)。
于是从 v 引燃能烧到的点,就是"从 v 出发存在一条权值严格递减路径"的结点集合。
关键观察:沿火路径权值严格递减 ⟹ 火走过的地方永远回不去。所以在树上,从 v 的每个"更小的邻居"出发的那些分支彼此互不重叠,可以直接相加。
设 R[v] 表示从 v 引燃能烧掉的结点数,则R[v] = 1 + Σ R[u](求和范围:u 是 v 的邻居且 aᵤ < aᵥ)。
把结点按权值从小到大排序,依次算 R 即可——因为算到 v 时,所有"更小的邻居"都已经算完了。

🔍 关键词提取

严格递减扩散树形 DP按权值排序分支互不重叠避免递归爆栈

已知条件

项目说明
输入第一行 n;第二行 n 个正整数 aᵢ;随后 n − 1 行每行 uᵢ, vᵢ
输出一个正整数:最多燃烧的结点个数
数据范围1 ≤ n ≤ 10⁵,1 ≤ aᵢ ≤ 10⁶
图的性质是一棵树(连通、n − 1 条边、无环)
扩散条件只能扩散到权值严格更小的相邻结点
初始选择可以任选一个结点引燃,取最优

需要解决的问题

02
思维导图
整理解题思路的全貌
🔥 R[v] = 1 + Σ R[u](只累加 aᵤ < aᵥ 的邻居)
🧠 关键观察
火只能沿"严格下坡"走
路径权值严格递减 ⟹ 永不回头
从 v 出发的燃烧集合 = 各下坡邻居分支的并
树上路径唯一 ⟹ 分支互不重叠
📐 递推式
R[v]:从 v 引燃能烧掉的点数
R[v] = 1(自己)+ Σ R[u]
只算 aᵤ < aᵥ 的邻居
同权值不算(题目要求严格小于)
🔁 计算顺序
把结点按 a 从小到大排序
处理 v 时更小的邻居都已算完
一趟 O(n + m) 累加
排序带来 O(n log n)
⚠️ 易错点
写成 ≤ 或 < 方向搞反
用递归 DFS(n = 10⁵ 会爆栈)
每个起点都 BFS 一遍(O(n²) 超时)
忘记取 max,答案至少为 1
03
样例手算推导
样例的完整推演

🧮 样例 1:n = 5,a = 6 2 3 4 5(边 1-2, 2-3, 2-5, 1-4)

邻接表:1 → {2, 4},2 → {1, 3, 5},3 → {2},4 → {1},5 → {2}。按权值升序依次算 R:

处理次序结点 vaᵥ权值更小的邻居(aᵤ)累加的 R[u]R[v]
122无—1
2332(a = 2)R[2] = 12
344无(邻居 1 的权值 6 更大)—1
4552(a = 2)R[2] = 12
5162(a = 2)、4(a = 4)1 + 1 = 23

R = [3, 1, 2, 1, 2],最大值 3 ✓ 与样例一致

1
手工模拟:从结点 1(权值 6)引燃

引燃 1(6)

1 的邻居:2(2 < 6)✓ 点燃,4(4 < 6)✓ 点燃

2(2)的邻居:1(6)、3(3)、5(5)都 ≥ 2 → 熄火

4(4)的邻居:1(6)≥ 4 → 熄火

烧掉的集合 = {1, 2, 4}

✅ 共 3 个,正是 R[1] = 3

2
为什么结点 2 只烧 1 个?

引燃 2(权值 2),它的邻居权值 6、3、5 全部更大

火一步都扩散不出去

R[2] = 1 + 0 = 1 ✓

✅ 只有权值最小的点才会"烧不动"

📊 逐点验证:所有起点的燃烧结果

引燃点燃烧集合个数与 R[v] 对照
1{1, 2, 4}3R[1] = 3 ✓
2{2}1R[2] = 1 ✓
3{3, 2}2R[3] = 2 ✓
4{4}1R[4] = 1 ✓
5{5, 2}2R[5] = 2 ✓
🔑
注意 R[3] 与 R[5] 的"复用":从 3 引燃时,火烧到 2(因为 2 < 3),而"从 2 还能烧多少"早就被算成 R[2] = 1 了,直接拿来用即可。
这就是"按依赖顺序递推"的威力:同一段子树的结果只算一次,避免了对每个起点重新搜索。

🧮 严格递减带来的"分支互不重叠"

还是样例 1,从结点 1 引燃时,两个下坡邻居 2(权值 2)和 4(权值 4)各自烧出的集合分别是 {2, 3, 5} 与 {4},它们唯一的联系是 1,而 1 的权值最大、火回不去,所以两个集合毫无重叠——直接相加就是总点数 1 + 1 + 1 = 3。

1
反证:分支为什么不可能重叠

设有结点 x 同时被"2 这一支"和"4 这一支"烧到

树上 2 到 x、4 到 x 的唯一路径都必须经过 1

于是从 x 要烧回 1,需要 a₁ < a 上某个更靠近 x 的点

但 a₁ = 6 比路径上所有点都大,矛盾

所以两支没有交点

✅ Σ 相加 = 并集大小

2
如果题目改成"小于等于"会怎样

同权值的点会互相点燃,形成连通块

火还能在块内来回走,甚至从低权值点回到 v

"回不去"的前提被破坏,Σ 相加不再成立

此时需要先对同权值连通块缩点,再在块间 DP

⚠️ 严格小于是本解法的地基

⚠️
别把"最多烧几个点"当成"最长递减路径有多长":燃烧是同时沿所有下坡方向铺开的,所有分支都要加起来(Σ),而不是只挑最长的一条(max)。
样例 1 中从 1 出发,两条链各只有 2 个点,但合起来是 3 个——如果写成 max 就会得到 2,答案错误。
04
解法对比
按权值升序递推 vs 每个起点搜索

⚔️ 解法对比

🟢 按权值升序递推(推荐) 推荐

R[v] = 1 + Σ R[u](aᵤ < aᵥ),把结点按权值排序后一趟算完

  • 时间 O(n log n)
  • n = 10⁵ 时约 1.7 × 10⁶
  • 完全不用递归,天然不爆栈
  • 代码约 30 行
💡
为什么升序就够:R[v] 只依赖权值更小的邻居,而这些邻居在升序序列里排在 v 前面,所以扫到 v 时它们的 R 早已就绪。这就是"按依赖顺序递推"的典型套路,等价于在 DAG 上按拓扑序 DP。

🟠 枚举起点 + DFS/BFS 模拟燃烧

对每个起点沿"严格下坡"搜一遍,统计燃烧点数

  • 时间 O(n²)
  • n = 10⁵ 时约 10¹⁰
  • 链形数据必超时
  • 递归实现还可能爆栈
⚠️
为什么"记忆化"也救不了:每个起点的燃烧集合都不一样,没法整体复用(火的方向依赖起点)。而 R[v] 这个状态是"对任何起点都成立"的局部量——找到这种可复用的状态,才是本题的关键一步。

📈 性能对比

方案复杂度可行性
按权值升序递推O(n log n) ≈ 1.7 × 10⁶✅ 瞬间
每个起点 BFS/DFSO(n²) ≈ 10¹⁰❌ 超时
记忆化搜索(按 a 排序)O(n log n)✅ 与递推等价,但要写迭代
05
算法流程图
按权值升序算出所有 R[v]
开始读入 n、点权 a[1..n] 与 n − 1 条边,建立邻接表把结点按权值从小到大排序,得到处理次序 ord按 ord 取出下一个结点 vR[v] = 1 + Σ R[u]:u 是 v 的邻居且 a[u] < a[v]用 R[v] 更新答案(取较大值)所有结点都处理完了吗?还有 ✓回到"取出下一个结点 v",继续递推处理完 ✗输出答案输出最多能燃烧的结点数取下一个结点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔥 最多能烧掉多少结点

第一行输入 n,第二行输入 n 个点权,随后 n − 1 行输入一条边。程序按权值升序算出每个 R[v],并(在规模较小时)用逐点搜索验证。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(按权值升序递推,无递归)

#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005], R[100005], ord[100005];
vector<int> g[100005];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) ord[i] = i;
    sort(ord + 1, ord + n + 1, [](int x, int y) { return a[x] < a[y]; });  // 权值升序

    int ans = 0;
    for (int t = 1; t <= n; t++) {
        int v = ord[t];
        int sum = 1;                                   // 自己一定会被烧掉
        for (int u : g[v]) {
            if (a[u] < a[v]) sum += R[u];              // 只累加"更小"的邻居
        }
        R[v] = sum;
        ans = max(ans, sum);                           // 题目问"选哪个点最优"
    }

    printf("%d\n", ans);
    return 0;
}
🔑
这段代码里没有任何 DFS/BFS:因为 R[v] 的依赖关系已经被"权值升序"排好了,直接按这个顺序扫一遍即可。
好处有两个:一是不会爆栈(n = 10⁵ 的链也没问题);二是每个 R[v] 只算一次,总工作量是"每条边看两次",非常轻。

📖 关键几行怎么看

代码作用为什么这样写
sort(ord + 1, ord + n + 1, cmp)确定递推顺序按权值升序,保证算 R[v] 时更小的邻居都已就绪
int sum = 1;计入自己任何点引燃至少烧掉自己,所以答案 ≥ 1
if (a[u] < a[v]) sum += R[u];核心转移严格小于才扩散;各分支互不重叠所以直接相加
ans = max(ans, sum);取最优题目问的是"最优起点",不是某个固定点的答案
⚠️
四个坑:① 判断写成 a[u] <= a[v]:同权值会互相点燃,答案偏大;② 用递归 DFS 求 R(n = 10⁵ 的链会爆栈,排序递推天然没有这个问题);③ 忘记取 max,直接输出 R[ord[n]] 或 R[1];④ 把燃烧总数写成"最长递减链长度"(多个分支要相加而不是取最大)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5
6 2 3 4 5
1 2
2 3
2 5
1 4
3题面样例(R = [3, 1, 2, 1, 2])
1
7
1只有一个结点,烧自己
3
1 1 1
1 2
2 3
1权值全相同:火一步都扩散不出去
4
4 3 2 1
1 2
2 3
3 4
4严格递减链:从 1 一路烧到底
4
1 2 3 4
1 2
2 3
3 4
4严格递增链:从 4 反向烧到 1
4
1 9 1 1
2 1
2 3
2 4
4中心权值最大:两个分支相加
3
1 3 2
1 2
2 3
3中间点最大,向两侧同时扩散
✅
自查清单:① 判断是"严格小于"吗?② 按权值升序递推(不递归)吗?③ 最后取了 max 吗?④ 用 Σ 而不是 max 合并分支吗?

🚨 易错点清单

⚠️
用了 ≤ 而不是 <:题目要求"严格小于",同权值不能互相点燃;改成 ≤ 会让等权结点连成一片,答案偏大。
⚠️
递归 DFS:n = 10⁵ 且是长链时递归深度 10⁵,会爆栈(应改成排序递推或显式栈迭代)。
⚠️
每个起点搜一遍:O(n²) 在 n = 10⁵ 时约 10¹⁰,必然超时。
⚠️
把 Σ 写成 max:燃烧是所有下坡分支同时铺开,必须相加。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log n)
空间复杂度
O(n)
n 最大
10⁵
总运算量
约 1.7 × 10⁶

时间怎么算的?

空间都用在哪?

邻接表存放 2(n − 1) 条有向边,外加 a、R、ord 三个长度 n 的数组。

✅ 约 170 万次操作,瞬间完成。相比"每个起点搜一遍"的 10¹⁰,快了四个数量级。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心观察:火沿"严格下坡"扩散 ⟹ 路径权值严格递减 ⟹ 回不了头
// 于是各下坡分支互不重叠,可以相加
// R[v] = 1 + Σ R[u]      (u 是 v 的邻居, a[u] < a[v])

// 计算顺序:按权值升序(同权值之间互不贡献,谁先谁后都一样)
for (int i = 1; i <= n; i++) ord[i] = i;
sort(ord + 1, ord + n + 1, [](int x, int y) { return a[x] < a[y]; });
for (int t = 1; t <= n; t++) {
    int v = ord[t], sum = 1;
    for (int u : g[v]) if (a[u] < a[v]) sum += R[u];
    R[v] = sum; ans = max(ans, sum);
}

// 若改成"最长递减链长度"(只挑一条链):
//     R[v] = 1 + max{ R[u] : a[u] < a[v] }
// 注意 Σ 与 max 的区别:本题是"全铺开",只问一条链时才用 max

// 若改成"小于等于":先对同权值连通块缩点(并查集),
// 得到块间的 DAG 后再按块权值升序 DP

// 面对"方向受限"的树上问题,常用思路:
//   1) 找到只依赖"更小/更大"邻居的状态
//   2) 按值排序,一次扫完(等价于 DAG 拓扑序 DP)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
按值排序递推获得无后效的依赖顺序依赖关系 DP、拓扑排序、Kruskal 缩边
受限方向求和R[v] = 1 + Σ R[u]树上"只能朝某个方向走"的计数问题
分支互不重叠树上路径唯一 + 严格递减树形 DP 的分支合并思想
迭代代替递归排序递推几乎不耗额外空间n = 10⁵ 深链、防爆栈
🌟
思考题:如果题目改成"可以扩散到权值小于等于自己的相邻点",答案怎么求?(提示:此时同权值的连通块会整体烧掉,因为块内可以互相点燃;先把同权值连通块用并查集缩成一个点,块的大小就是"烧掉的基数";再把块之间"严格递减"的边连成一张 DAG,按块权值升序做 R[块] = size[块] + Σ R[子块],取最大值即可。从"严格"变成"非严格",通常就意味着一轮缩点/并查集。)