AGC008F - Black Radius

题意：

给定一棵 $n$ 个节点的树，每一个节点有一个权值 $0$ 或 $1$。问有多少个本质不同的树上集合，满足其是某一个权值为 $1$ 的点的 $d$ 邻域。点 $x$ 的 $d$ 邻域定义为所有到 $x$ 的距离不超过 $d$ 的点的集合。称 $d$ 为邻域的半径。

$1\le n\le 2\times 10^{5}$

部分分：所有集合的权值均为 $1$。

标签：

树形 DP，计数。

解法：

子树的深度定义为最深点到子树根的路径上的边数。

先考虑部分分怎么做。此时即要求树上有多少个本质不同的邻域。

先考虑邻域为全集的情况。为了不让全集被计算多次，我们限定每一个点的邻域不能为全集，最后答案加上全集。若点 $i$ 的子树中最深的深度为 $f_i$，次深子树的深度为 $g_i$，那么显然邻域半径必须小于 $f_i$。

考虑两个邻域何时会算重：若树上有一条边 $(u,v)$，假设 $u$ 是根。若 $v$ 的 $d$ 邻域覆盖了整个 $u$ 除 $v$ 以外的子树，那么这个邻域与 $u$ 的 $d-1$ 邻域是相同的，且 $v$ 必定是 $f_u$ 所在的子树（否则无法覆盖其余子树）。这启示我们，对于每一个邻域，在使其半径最小的中心计算。容易发现，半径最小时，邻域的中心是确定的。

考虑每一个点 $i$ 为根，考虑其作为邻域的中心时对答案的贡献。其为邻域中心时，其半径不能太大。设其最大半径为 $d$，则 $f_u$ 方向儿子的 $d-1$ 邻域不能覆盖 $u$ 的其它所有儿子。其它儿子中最远的到 $v$ 点距离是 $g_u+1$，即 $d-1< g_u+1$，解得 $d< g_u+2$。$d$ 再和 $f_u-1$ 取 $\min$，防止取到全集。$i$ 的邻域半径即为 $[0,\min(f_u-1,g_u+1)]$。

当有一些点权值为 $0$ 的时候，其合法邻域半径的下界不再是 $0$。但是有一些合法邻域仍然以 $i$ 的中心，仍然在 $i$ 计算这些合法邻域的贡献。

以 $i$ 为根，若 $val_i$ 为 $1$，直接套用部分分的做法。否则，有 $i$ 可能有半径大于等于某个值 $d$ 的邻域也是合法的。考虑如何求这个 $d$。以 $i$ 为根时，若某个儿子 $v$ 的子树中存在 $val$ 为 $1$ 的点，则当 $d\ge f_v+1$ 时，这个点的 $d$ 邻域的中心就是 $i$ 了。所以只要求出 $h_i$ 表示 $i$ 点所有儿子中，有可选点的最深子树的深度最小值。

那么可行半径范围就是 $[h_i,\min(f_i-1,g_i+1)]$。

换根 DP 即可求出答案。