再见 LCT

G

本题首先转化，如果两路径不交（无公共点），则必然可以存在一条边，使得这条边可以分割选择的路径。

不难发现，这很有前途。于是枚举断边 $(u, v)$。$u$ 是 $v$ 的父亲。依题，我们只关心选择的路径长度，所以又发现长度大的路径存在，则长度比他小的路径必然存在。故转化成直径问题。

在 $v$ 的子树中找直径（不必经过 $v$），在 $\mathcal{subtree}(1)\ - \ \mathcal{subtree}(v)$ 的连通块中找直径（"-" 是差集的意思）。

前者是简单的。重点考虑后者。

你不会以为要 DS 吧。

先分类，直径有以下 $3$ 种情况。

• 过 $u$
• 路径 lca 位于 $u$ 的子树
• 其他情况

第一种情况，容易发现，维护 $g_{i}$ 表示 $i$ 出发，若第一步走到 $i$ 父亲，他的最长能走几步？转移时容易的。自证不难。

第二种情况，记录 $d_{i}$ 表示 路径 lca 在 $i$ 子树的路径长度最大值。转移依旧简单。注意判断防止非法。

第三种情况，维护 $h_{i}$ 表示 $i$ 子树外，最长的路径，转移仍旧简单。

$h_i = \max\{h_{fa},$经过 $fa$ 但不经过 $i$ 的最长路径$\}$。

最后，答案是依旧简单的.

建议降下去 蓝。

我不是红磷！