广义圆方树

· · 算法·理论

圆方树刻画的是点双缩点后的结构。具体来说,我们用方点来代表一个点双,在方点下挂圆点表示点双中的点。

对于广义圆方树,我们要求圆点和方点间隔连接。贺一下 OI-Wiki 上的图

考察两个圆点 u,v,在圆方树上拉出树链,则树链上的圆点表示无向图 u \to v 简单路径的必经点。更进一步,u \to v 在圆方树上形成的毛毛虫的虫身是必经点,虫足是可以经过的点,毛毛虫以外的点不可能经过。

下文只讨论原图连通且不为单点的情形。可以使用如下 Tarjan 算法建圆方树:

int dn, cnt, dfn[N], low[N];
stack<int> st;
void tarjan(int u) {
    dfn[u] = low[u] = ++dn, st.emplace(u);
    for (int v : e[u]) {
        if (!dfn[v]) {
            tarjan(v), chkmin(low[u], low[v]);
            if (low[v] != dfn[u]) continue;
            int x; add(u, ++cnt);
            do x = st.top(), st.pop(), add(x, cnt);
            while (x != v);
        } else {
            chkmin(low[u], dfn[v]);
        }
    }
}

由于点双的数目 < n,圆方树的点数 \le 2n-1,注意数组大小开两倍。

建出圆方树后,我们可以刻画原图的点双和边双在树上的形态:

至此,使用广义圆方树 & DFS 生成树就足以刻画大部分无向图连通性问题。

CF487E Tourists

建立原图的广义圆方树,变成单点修改,询问一条毛毛虫的点权 \min,毛毛虫剖分即可。

上面的做法有点魔怔,考虑将圆点的权值挂在方点上,方点开个 multiset 维护,树剖线段树维护树链最小值即可。

P4606 [SDOI2018] 战略游戏

建立原图的广义圆方树,并对询问的点集建虚树,答案就是虚树的圆点数目。

根据经典结论,只要求出两两 dis 之和的一半即为答案。