首先要一种能在 \(\log n\) 时间复杂度求路径 \(mex\) 的方法。
我们先把所有点的编号加一，从 \(1\) 开始。我们再记 \(l_u\) 表示 \(u\) 属于 \(1\) 的哪个儿子的子树中。（特别的 \(l_1=1\)）
然后我们考虑一条路径 \(u,v\) ，如果 \(lca(u,v)\not =1\) 那么显然是可以直接不用管的。
我们考虑 \(lca(u,v)=1\) 的情况
我们需要算出三部分答案：
-
\(l_u\) 子树中，除去 \(u\) 到 \(l_u\) 路径上的点编号上最小值。
-
\(r_u\) 子树中，除去 \(v\) 到 \(l_v\) 路径上的点编号的最小值。
-
除去 \(l_u,l_v\) 两棵子树，点编号的最小值。
我们先考虑第三条，我们定义一个子树的权值为这棵子树编号的最小值。
那么我们找出前三小，那么答案一定可以从中得到。
考虑前两条，实际上是本质相同的，考虑其中一个怎么求。
那么我们求一个除了一条路径外，实际上就是求一段前缀和后缀的编号最小值，我们记作 \(f_u\) 可以在线性复杂度内轻易求出。
所以我们就可以在 \(O(\log n)\) 复杂度内求出一条路径的 \(mex\) （预处理 \(O(n)\) ，求 \(lca\) 要 \(\log\)）