P9052 题解

lcjqwq · 2023-06-21 18:57:07 · 题解

我们考虑如何处理一对询问 (A,B)。我们把过程看作是先把 B 点删掉，如果一个点此时没有出度，那我们就继续把这个点也给删掉。一直这样进行下去。如果最后 A 被删掉了，那么 (A,B) 就能成为答案。

对于当前选择的根，如果删掉点 u 后会导致 v 点也被删除，我们称其为 u 支配点 v。我们可以构建出支配树：考虑一个点的所有出度，他们在支配树上的 LCA 就是它的父亲。

需要注意的是，根可能支配自己。根的所有出度如果都会被自己删掉那么他们在支配树上的 LCA 就会支配根。所以实际上，我们最后得到的关系是一个支配基环树。对于环上的每个点，我们如果删掉他就会让这个基环树被删掉；对于不在环上的点，删掉它会使得子树里的点被删掉。

可以发现，我们可以把一个图变成基环树森林再统计答案。考虑按 k 从 1 枚举到 n 动态的维护基环树森林的形态。最开始的图是 n 个自环，每次我们枚举到点 u 我们就把这个自环去掉，他的出边都加到图中。

可以发现 u 之前一定是某颗树的根。

• 如果当前这个点 u 的出度都在自己这颗树里，把他们的 LCA 往 u 连一条边就好了。
• 如果所有出度都在另一颗树中，同样求出 LCA，我们现在就是是把 u 的子树接到 LCA 下面。
• 如果出度分散在不同的联通块，此时 u 并不任何点支配。但是随着合并的进行，可能在某一刻，u 的出边全都在某一个联通块里了。所以我们在加入 u 的时候往每个联通块里扔一个标记，每次合并两个联通块的时候把两个联通块都有的标记的计数器减一，减到 0 就需要把 u 重新拿出来，把出度的 LCA 和它连边。我们可以考虑用线段树合并维护这个过程就可以做到单 log。每次在 merge 两个叶子的时候处理一下计数器。开一个队列记录当前需要考虑的 u，每次拿队首出来做。计数器变成 0 就 push 进去。

考虑怎么算答案，即对于每个时刻的支配森林求出有多少个点对 (u,v) 满足 u 能到达 v。

答案就是每个点的 siz 和也就是 dep 和，我们要维护的操作是把一个树根接到某个点的儿子处。考虑在 LCT 上维护 Link，求某个点的 dep，求 LCA，求联通块 siz 的操作就可以做了。

如果过程中出现了一个新的基环树，需要特殊处理一下。由于每个联通块只会变成一次基环树，我们可以直接暴力的通过某些手段 O(siz) 的处理这颗基环树的答案。

但是要注意的是，一颗基环树虽然不会再往外连出出度，但是里面的点之后有可能作为其他的点的出度。为了方便后续的答案计算，需要把基环树上的环点的 dep 人为的修改一下。具体的，把根的 dep 改为环长，其他环点的 dep 改成 0 就好啦。

以及，每颗树的树根有可能编号大于当前枚举的 k。可以最开始每个点的 dep 设成 0，加入这个点的时候加上对答案的贡献，再把 dep 改成 1，这样算出来的 dep 才是对的。

总体的时间复杂度为 O(m \log n)。可以发现这颗 LCT 由于 Link 操作都是把一个树根接到另一个儿子上所以只需要 access 而不需要维护懒标记进行 makeroot，常数是很美丽的。

另一个做法，我们可以先直接求出 k=n 时的基环森林。再考虑在最后的状态上统计答案。

首先应该怎么求出 k=n 时的状态呢？如果我们现在有一个根，我们可以直接在图上模拟一遍求 LCA 加边的过程，用倍增维护就好。但是我们不能暴力的枚举一个根然后做一遍这样的事情。因为一个点为根的支配树可能是另一个点为根的支配树的子树。所以问题就变为了找到那些最厉害的根。

我们考虑不断的缩图。考虑一个点 u，如果他只有一条出边连向 v，那么我们就可以把 u 扔了，因为 v 的支配树一定包含他的支配树。此时我们把 u,v 缩成一个点，并且把之前连向 u 的边全部接到 v 上。重复这个过程，直到图中每个点的出度都 \ge 2。此时图中的每个点都可以成为一个根/一个基环树环里的某个点。

维护缩图的过程可以使用线段树合并，可以发现和第一个做法中维护的信息大同小异，每个联通块的根处维护有那些点连向他，每次合并的时候相当于把两者都有的点的出度减一，每次找到出度变为 1 的那些点执行合并操作即可。

之后我们考虑怎么求出每个 k 的答案。首先可以发现每个时刻的图都是最后的图的子图，并且每条边都是在 k 逐渐增大到某个值的时候出现。这个值可以在求出基环树的过程中维护出来。具体来说，考虑构建基环树的过程中考虑到了当前点 u 以及他的出度的 LCA，u 连向 LCA 的这条边就是 u 到 LCA 上的每一条链上的所有边的权值的 max。于是我们在倍增的时候多维护一个链上权值的 max 即可。

之后考虑统计答案。我们拎一个环上的点当根搞一颗外向树。这个图会存在至多一条返祖边。我们把答案分为直上直下和必须经过返祖边的两部分进行统计。

• 对于直上直下的部分，可以并查集维护 siz 和最浅的那个点，很好做。
• 对于经过返祖边的部分，我们可以巧妙地把最开始钦定的根设置成使得那个返祖边是环上边权最大的边的那个点。这样我们就能保证在加入返祖边的时候，整个环就完整的形成了。
  • 加入返祖边之前只有直上直下的贡献。
  • 加入返祖边时，由于只会加入一次，我们可以暴力的 DFS 一遍算贡献。
  • 加入返祖边后，可以发现如果一对 (u,v) 满足从 u 走到 v 必然要经过返祖边那么一定是形如 u 处于 v 在环上的投影以下一直到返祖边端点的那一条链上。于是也可以很方便通过并查集的 siz 信息计算贡献。

最后整体的时间复杂度依然是 O(m \log n)，来源于线段树合并以及倍增求基环树。

代码(LCT做法)：https://www.luogu.com.cn/paste/21uo8ogi