题解：P15947 [JOI Final 2026] 集邮 5 / Collecting Stamps 5

CuteSheep128 · 2026-11-10 16:12:46 · 题解

在模拟赛中背景改成了帽子工厂状物。煤球是白的。

典。

首先这个题目有点分治的风味。

先风味一下。现在问题变成，有一个分治中心。

我们接下来要解决的问题是：

对于每个点求出经过分治中心的所有路径中，符合条件的路径。

考虑 u 在到分治中心的途中是否盖章。

这个判断方法很简单，只要记 f_i 表示从 i 子树的后代中，至少要走多少条边才能盖章。

然后 f_{u}=\min(f_{fa_u}-1,a_u)。

然后约束就只剩下了深度。可以简单做。

对于到分治中心往外走的时候，你发现一个终点的对应的起点约束是深度的一个区间。差分后做完了。