选一个结点引燃,火只从燃烧点扩散到权值严格更小的相邻点,求最多能烧掉多少结点。
小杨有一棵包含 n 个结点的树,结点 i 的权值为 aᵢ。他可以选择一个结点引燃;每个燃烧的结点会把火扩散到它的相邻结点中权值严格小于自身的那些结点,直到不再有新结点被引燃。
问:合理选择初始结点时,最多可以燃烧多少个结点?
R[v] 表示从 v 引燃能烧掉的结点数,则R[v] = 1 + Σ R[u](求和范围:u 是 v 的邻居且 aᵤ < aᵥ)。严格递减扩散树形 DP按权值排序分支互不重叠避免递归爆栈
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个正整数 aᵢ;随后 n − 1 行每行 uᵢ, vᵢ |
| 输出 | 一个正整数:最多燃烧的结点个数 |
| 数据范围 | 1 ≤ n ≤ 10⁵,1 ≤ aᵢ ≤ 10⁶ |
| 图的性质 | 是一棵树(连通、n − 1 条边、无环) |
| 扩散条件 | 只能扩散到权值严格更小的相邻结点 |
| 初始选择 | 可以任选一个结点引燃,取最优 |
R[v] 只依赖"权值更小的邻居",升序处理时它们必定已经算好,一趟递推就完成,无需递归;同权值的点之间不能互相贡献,所以它们谁先谁后都不影响结果邻接表:1 → {2, 4},2 → {1, 3, 5},3 → {2},4 → {1},5 → {2}。按权值升序依次算 R:
| 处理次序 | 结点 v | aᵥ | 权值更小的邻居(aᵤ) | 累加的 R[u] | R[v] |
|---|---|---|---|---|---|
| 1 | 2 | 2 | 无 | — | 1 |
| 2 | 3 | 3 | 2(a = 2) | R[2] = 1 | 2 |
| 3 | 4 | 4 | 无(邻居 1 的权值 6 更大) | — | 1 |
| 4 | 5 | 5 | 2(a = 2) | R[2] = 1 | 2 |
| 5 | 1 | 6 | 2(a = 2)、4(a = 4) | 1 + 1 = 2 | 3 |
R = [3, 1, 2, 1, 2],最大值 3 ✓ 与样例一致
引燃 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),它的邻居权值 6、3、5 全部更大
火一步都扩散不出去
R[2] = 1 + 0 = 1 ✓
✅ 只有权值最小的点才会"烧不动"
| 引燃点 | 燃烧集合 | 个数 | 与 R[v] 对照 |
|---|---|---|---|
| 1 | {1, 2, 4} | 3 | R[1] = 3 ✓ |
| 2 | {2} | 1 | R[2] = 1 ✓ |
| 3 | {3, 2} | 2 | R[3] = 2 ✓ |
| 4 | {4} | 1 | R[4] = 1 ✓ |
| 5 | {5, 2} | 2 | R[5] = 2 ✓ |
还是样例 1,从结点 1 引燃时,两个下坡邻居 2(权值 2)和 4(权值 4)各自烧出的集合分别是 {2, 3, 5} 与 {4},它们唯一的联系是 1,而 1 的权值最大、火回不去,所以两个集合毫无重叠——直接相加就是总点数 1 + 1 + 1 = 3。
设有结点 x 同时被"2 这一支"和"4 这一支"烧到
树上 2 到 x、4 到 x 的唯一路径都必须经过 1
于是从 x 要烧回 1,需要 a₁ < a 上某个更靠近 x 的点
但 a₁ = 6 比路径上所有点都大,矛盾
所以两支没有交点
✅ Σ 相加 = 并集大小
同权值的点会互相点燃,形成连通块
火还能在块内来回走,甚至从低权值点回到 v
"回不去"的前提被破坏,Σ 相加不再成立
此时需要先对同权值连通块缩点,再在块间 DP
⚠️ 严格小于是本解法的地基
R[v] = 1 + Σ R[u](aᵤ < aᵥ),把结点按权值排序后一趟算完
对每个起点沿"严格下坡"搜一遍,统计燃烧点数
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 按权值升序递推 | O(n log n) ≈ 1.7 × 10⁶ | ✅ 瞬间 |
| 每个起点 BFS/DFS | O(n²) ≈ 10¹⁰ | ❌ 超时 |
| 记忆化搜索(按 a 排序) | O(n log n) | ✅ 与递推等价,但要写迭代 |
第一行输入 n,第二行输入 n 个点权,随后 n − 1 行输入一条边。程序按权值升序算出每个 R[v],并(在规模较小时)用逐点搜索验证。
点按钮开始 →
#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; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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];④ 把燃烧总数写成"最长递减链长度"(多个分支要相加而不是取最大)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 3 | 题面样例(R = [3, 1, 2, 1, 2]) |
1 | 1 | 只有一个结点,烧自己 |
3 | 1 | 权值全相同:火一步都扩散不出去 |
4 | 4 | 严格递减链:从 1 一路烧到底 |
4 | 4 | 严格递增链:从 4 反向烧到 1 |
4 | 4 | 中心权值最大:两个分支相加 |
3 | 3 | 中间点最大,向两侧同时扩散 |
邻接表存放 2(n − 1) 条有向边,外加 a、R、ord 三个长度 n 的数组。
✅ 约 170 万次操作,瞬间完成。相比"每个起点搜一遍"的 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⁵ 深链、防爆栈 |
R[块] = size[块] + Σ R[子块],取最大值即可。从"严格"变成"非严格",通常就意味着一轮缩点/并查集。)