[AGC008F] Black Radius

缕一缕大概思路。

首先假设所有点都被喜欢。

一个集合可能被多个 \((u,d)\) 表示出来，我们取最小 \(d\)，只有在全集的时候一个最小 \(d\) 可能会有多个 \(u\) 进行对应，所以我们去掉对全集的统计。

接着考虑以一个点为中心的充要条件。

设为 \((u,d)\)，首先 \(d\) 不能太大，否则会超出全集。

其次 \(d\) 还是不能太大，否则可能被一个更小的 \(d\) 进行替代。

若能被替代一定是相邻的点 \((v,d-1)\) 进行替代，此时一定满足 \(u\) 的其他子树可以被 \(d-1\) 填满，这意味着除开 \(v\) 这一个子树其他子树的深度不超过 \(d-2\)，这也意味着不被替代必须满足 \(\text{2ndmxdep}\gt d-2\)，也就是 \(d\leq \text{2ndmxdep}+1\)。

设 \(f_u\) 是子树深度最大的深度，\(g_u\) 是第二大，则满足 \(d\leq \min(f_u-1,g_u+1)\)。

接着我们考虑有的点不被喜欢的情况。

这个时候我们需要将 \(u\) 满足的那些树留给另一个点进行统计。

若 \((u,d)\) 能被 \((v,t)\) 代替，由于 \(d\) 的最小性，\(t\gt d\)，既然如此，\(v\) 所在子树必须被 \((u,d)\) 填满，否则会延申出去。

我们统计 \(h_u\) 表示有喜欢的点的子树的最深的点的深度最小值，则必须满足 \(d\geq h_u\)。