题目

给定一张 $n$ 个点 $m$ 条边的图,求有多少个有序点对 $(a,b,c)$,使得存在一条 $a\to b\to c$ 且不经过重复点的路径。

$1\le n\le 10^5$,$1\le m\le 2\times 10^5$.

分析

这是道不好好分析会分类死的题目。

考虑建出圆方树,则原题条件等价于:求有多少个有序点对 $(a,b,c)$,使得存在一条 $a\to b\to c$,且不重复经过圆点,但可以重复经过方点的路径。

于是不难想象,我们枚举中转点 $b$,我们可以把 $b$ 相连的所有点(显然都是方点)与其合并,然后以 $b$ 为中转点的方案数即为在任意两个不同的子树中取两个点 $a,c$ 的方案数。

然后可以考虑容斥,先求出不考虑在不同子树内的方案,再求出在同一子树内的方案,然后用前者减去后者。

$$ \sum_i\sum_{j\neq i}s_is_j = \left(\sum_i s_i\right)^2 - \sum_is_i^2 $$

于是我们只需要维护,以每个点为根时,所有子树大小的平方和(显然,所有子树大小的和为当前连通块大小 $-1$)。

这可以用简单的换根求出,时间复杂度为 $\mathcal O(n + m)$,然后这道题就做完了。

代码

const int N = 5e5 + 5;

int n, m, b_cnt; ll ans;

int dfv, top, dfn[N], low[N], st[N], rt[N], siz[N];
std::vector <int> E[2][N];
void Add(int u, int v, int p) {
    E[p][u].push_back(v);
    E[p][v].push_back(u);
}
void Tarjan(int u, int r) {
    rt[u] = r;
    dfn[u] = low[u] = ++dfv;
    st[++top] = u;
    for(auto v : E[0][u]) {
        if(!dfn[v]) {
            Tarjan(v, r);
            low[u] = std::min(low[u], low[v]);
            if(low[v] == dfn[u]) {
                rt[++b_cnt] = r;
                for(int x = 0; x != v; --top) {
                    Add(b_cnt, x = st[top], 1);
                    ++siz[b_cnt];
                }
                Add(b_cnt, u, 1);
                ++siz[b_cnt];
            }
        } else low[u] = std::min(low[u], dfn[v]);
    }
}

int t_siz[N]; ll t_sq_s[N];
void Dfs(int u, int p) {
    if(u <= n) t_siz[u] = 1;
    for(auto v : E[1][u])
        if(v != p) {
            Dfs(v, u);
            t_siz[u] += t_siz[v];
            t_sq_s[u] += 1LL * t_siz[v] * t_siz[v];
        }
}
void Dfs2(int u, int p) {
    for(auto v : E[1][u])
        if(v != p) Dfs2(v, u);
    if(u <= n) {
        ll sq_s = 0;
        for(auto v : E[1][u])
            sq_s += t_sq_s[v];
        sq_s -= 1LL * t_siz[u] * t_siz[u];
        ll s_fa = t_siz[rt[u]] - t_siz[p];
        sq_s += s_fa * s_fa;
        ans += 1LL * (t_siz[rt[u]] - 1) * (t_siz[rt[u]] - 1) - sq_s;
    }
}

int main() {
    rd(n, m); b_cnt = n;
    for(int i = 1; i <= m; ++i) {
        int u, v; rd(u, v);
        Add(u, v, 0);
    }
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) {
            Tarjan(i, i);
            top = 0;
        }
    for(int i = 1; i <= n; ++i)
        if(rt[i] == i) Dfs(i, 0), Dfs2(i, 0);
    printf("%lld\n", ans);
    return 0;
}
最后修改:2021 年 03 月 22 日 06 : 06 PM