重点在于删除树边 (u,fa_u) 的情形。边双连通分量的好处是删除树边后仍然连通,并且我们只关心所有跨过 (u,fa_u) 祖先链的点,否则别的点必然上下连通,而“上部分”就与删除树边那一块连通。因此新的割点 x 只能是 u 子树内的点或者 u 的祖先。
此时 x\ne u,否则点 u 自身就会把 G' 分裂成进一步的点双。此时 G' 分为根减去 u 子树,u 子树减去 x 子树,以及 x 的一堆子树。将其称为上,中,下。如果上和中有返祖边连接,此时 (u,fa_u) 是否删去无所谓,x 不可能成为割点;接下来上,中是不连通的。此时 x 成为割点当且仅当不存在 x 某个儿子 s_i 的子树同时与上,中部分连通。
此时考虑下端点在 s_i 子树,上端点在 x 祖先的返祖边的上端点的深度,其对应区间 [l,r],就要求 dep_u\leq l 或者 dep_u>r。对于一个 x,考虑其所有 s_i,就可以得到 \mathcal O(\deg_x) 个限制区间使得 u 的深度不能在限制区间中。关于上,中部分没有边的限制,求出所有下端点 v_i 在 u 子树,但是上端点为 u 祖先的 v_i 的 \text{lca}=d(由于 G' 点双连通,所以 d 存在)。其中 d 的维护可以使用树上并查集从下往上维护,也可以描述成深度区间的限制。然后使用线段树,维护 dfs 序,并且支持区间加区间最小值个数即可维护。
特判掉 x 为树根的 corner case。此时 G' 分为根减去 x 子树,x 子树减去 u 子树以及 u 子树,还是分为上中下三部分。我们要求下面不同时与中和上连通。分为下端点在 u 子树的返祖边的上端点均在 x 或比 x 更深的位置;以及均在 x 或者比 x 更浅的位置。