P3398 仓鼠找 sugar 做题记录

给定一棵树，多组询问，每次询问给定四个点 $a,b,c,d$，求 $a\to b$ 和 $c\to d$ 这两条路径是否有交。

有个结论：若树上两条路径 $a\to b$ 和 $c\to d$ 有交，那么令 $\operatorname{lca}(a,b)=x,\operatorname{lca}(c,d)=y$，要么 $x$ 在 $c\to d$ 上，要么 $y$ 在 $a\to b$ 上。

证明如下：

把 $a,b,x$ 画出来：（写文章时图论编辑器上不去……）

容易发现，$x$ 把它的子树“堵住”了，想要进去就必须经过它。但 $a\to b$ 肯定在 $x$ 的子树内，所以子树外面的链想和 $a\to b$ 相交就一定要经过 $x$。

还有一种可能就是 $c\to d$ 在 $x$ 的子树内，不难发现此时的情况相当于把 $a\to b$ 和 $c\to d$ 这两条路径交换。

综上，得证。

所以根据结论判断即可。判断一个节点是否在链上可以用这个节点到链两端的长度是否等于链的长度来做。