题解：P10304 [THUWC 2020] 道路修建

OccDreamer · 2024-04-03 21:52:03 · 题解

设 f_i 表示 i 这个点的父亲。

首先考虑一个询问 (a,b) 不能到达的点肯定是 b 子树中包含 b 的一个连通块。

假设对于一个询问 (a,b) 而言，能到达的 b 子树内的点是集合 S，那么如果我们对于 f_i \notin S，将 f_i \to i 这一条边断掉是完全不会影响答案的。

设 g_i 表示在 1 \to i 的路径上断掉一个后缀最长能断多长的后缀使得仍然存在 1 到 i 的路径。

具体的，假设倍增到 j 这个点，我们访问所有的横叉非树边 (x,i)，用 \text{lca}(i,x) \to x 这一段的 g 去 check 是否合法，访问所有的从祖先连过来的非树边 (x,i) 用 g_x 去 check，这所有的 g 中只要有一个合法就可行。

查询一段 g 可以倍增维护。所以这一部分是 O((n+m) \log n) 的。

考虑接下来怎么做，对于一个询问 (a,b)，将这个询问挂在 a 这个点上。

然后按照题面给定的方式去 dfs 整棵树，假设现在在 x 号点，那么我们先将 g_i=x 的 i 进行一个子树加 1，设维护的这个和的数组是 v，

然后访问所有的询问 (x,b)。

考虑怎么知道上文提到的集合 S，我们设 u 为 1 \to b（不包括 b）路径上有多少个点的 g 的值是 a 的祖先，这个可以用 BIT 简单求出来（区间加，单点查），那么一个点 x \in S，那么 v_x>u，否则一定有 v_x=u。

首先根据 u 是 1 \to b 操作的点数，所以 v_i \geq u。

如果 v_i=x，那么 v 的总和全都是 1 \to b 上贡献的，也就是 1 能走到这些点，但是因为 x \to b 的边都断了，所以实际上这些点还不能对 b 子树进行贡献。

所以对于一个 (x,b) 的询问，只需查询 b 子树内的 v_i=u 的数量即可，线段树维护最小值以及最小值数量即可。

时间复杂度 O((n+m+q) \log n)。

代码写的有点丑，想要的私信。