@[Swiftie_wyc22](/user/285414) 巨大恶心分类讨论，可以借助虚树。
by 2020kanade @ 2023-01-26 09:01:32
当然有没有更好的办法证明就不知道了。
by 2020kanade @ 2023-01-26 09:02:13
反证
by Network_Error @ 2023-01-26 09:24:34
你考虑一个叫做 dfn 序的东西。
你考虑为何可以用 RMQ 解决 LCA，对此容易分析。
by myee @ 2023-01-26 09:31:58
@[Swiftie_wyc22](/user/285414) 考虑有三个点 $A,B,C$，对于 $X=lca(A,B)$，点 $C$ 只有可能在 $X$ 的子树内或者子树外（ $X=C$ 时显然）。
对于 $C$ 在 $X$ 子树外的情况，显然 $A$, $B$， 只能通过 $X$ 点往 $C$ 跳，所以 $lca(A,C)=lca(B,C)$ 。
对于 $C$ 在 $X$ 子树内的情况， $C$ 如果在 $A$ 子树内，则只能通过 $A$ 往 $B$ 跳，所以 $lca(A,B)=lca(C, B)$，在 $B$ 子树内同理。若都不在则任意两点的 $lca$ 均为 $X$ 。
得证。
by Magia @ 2023-01-26 10:09:01
@[Black_Porridge](/user/200060) 谢谢！看懂了！
by Swiftie_wyc22 @ 2023-01-26 10:28:37