[NFLS 1462/3] 岛屿 题解

大意

给定一个基环树森林, 求每棵基环树的直径之和.

题解

树上求直径很容易, 设 $f_u$ 为以 $u$ 在 $u$ 的子树中以 $u$ 为一端的最长链的值.

$f_u = max(f_v + w),\ \{v, w\} \in edges(u), v \not= fa_u$,

$res \leftarrow max(res, f_x + w_x + f_y + w_y),\ \{x, w_x\}, \{y, w_y\} \in edges(u), x, y \not= fa_u$

而基环树则要考虑环.

考虑破环为链, 再扩大一倍.

那么 $res \leftarrow max(res, f_i + f_j + len(i, j)), \ 1 \le i, j \le 2 * n, |j - i| \lt n$, 其中 $n$ 为环的长度.

使用前缀和, 贡献则变为 $f_j + len(1, j) + f_i - len(1, i)$.

考虑使用单调队列.

在队头, 每次弹出 $i - j \ge n$.

在队尾, 每次弹出 $g(j) < g(i)$, 其中 $g(x) = f_x - len(1, x)$.

每次用队头元素更新即可.