Luogu6071 [MdOI2020] Treequery

题意：给出一棵 个点的无根树，边有边权。

多次查询点 到点 的 条路径的交集的长度。

强制在线，，时限 。

---

• 观察：这条路径等价 到 的虚树的最短路径。

分类讨论：

• 1. 全部在 的子树内

  取他们的 LCA 到 的距离就好了。其实就是从虚树的根出发。

• 2. 全部不在 的子树内

  取虚树上最近的一个点连过来，具体咋搞后面再说。

• 3. 有一部分在 的子树内，另一部分不在

显然，得到的虚树包含 本身，答案为 。

---

以标号为版本轴，根据 dfs 序建立主席树。可以差分得到任意 点集的 dfs 序线段树 。

的子树可以表示成一个区间。

把 dfs 序分成三部分：。

首先查看是哪种情况：

• 如果 在 中有元素，且在 中有元素，则为 (3)。

• 如果仅 中有则为 (1)。

• 仅 中有则为 (2)。

对于 (3) 可以直接得出答案 。

对于 (1)，一个众所周知的结论是：点集的 LCA = dfs 序最大最小的两个点的 LCA.

对于 (2)，需要继续分类讨论。

• 路径先上后下

  路径的出发点一定是虚树的根，否则可以更短，我们判一下 是否在虚树的根的子树内即可。

• 路径直接向下

  可以相当于把 加入虚树,然后查看到父亲的边的长度。

  根据虚树的经典结论，分别查询 dfs 序前驱后继取个 min 即可。

总的来说，写一个 LCA 再写一个 dfs 序主席树即可，这里只需要求前驱后继。

复杂度 。