Luogu4899 [IOI2018] werewolf 狼人

题意：给出一张 个点 条边的简单无向图，点编号为 。

有若干个询问，给出 ，判定是否存在一条路径满足：

• 起点为 ，终点为 。

• 存在途经点 （路径写作 ），使得 不经过编号为 的点， 不经过编号为 的点。（点 被限制两次）

强制在线。，，时限 。

---

由于无向图，记从 出发，只经过 到达的集合为 ，从 出发，只经过 到达的集合为 ，若 和 有交，则存在所需的路径，否则不存在。

这是瓶颈路问题，考虑用 Kruskal 重构树来刻画 。

以 为例（限制经过的最小点权和，相当于最大生成树），传统的重构树权在边上，这题权在点上，我们可以将边权设为端点点权的 。

接下来，建立最大重构树， 就是它的某棵子树。 同理（只不过是最小重构树）。

---

问题转化为：给出两棵树 ，它们的叶子标号对应，每次各选一个子树，问有没有交集。

将第二棵树求出 dfs 序,然后挂在第一棵树的节点上，对第一棵树线段树合并，维护子树内的dfn 集合。

每次查询，在第一棵树的对应节点上，查询第二棵子树的对应 dfn 区间即可。

时间复杂度 ，空间。