P4630 铁人两项

圆方树上统计路径能够经过的原点

问题

P4630 [APIO2018] 铁人两项
在一张简单无向图中选择两两不同的起点 $s$、切换点 $c$ 和终点 $f$。若存在一条从 $s$ 出发、经过 $c$ 到达 $f$ 且不重复经过顶点的路径，这个有序三元组就合法，要求统计所有合法选择。

数据规模：$n\le10^5$，$m\le2\times10^5$，无自环和重边，原图不保证连通。

无向图，跟点相关的问题，不难想到点双连通分量。

假设图为 A - C - B AB 为两个点双，C 为割点，那么所有 A 中的点经过 C 都能到达所有 B 中的点。

于是可以建立圆方树：每个原图点作为圆点，每个点双连通分量作为方点，并把方点与分量内所有圆点连接。

设圆方树上 $s$ 到 $f$ 的路径经过若干方点，任意合法的 $s \to c \to f$ 简单路径只能经过这些点双；反过来，这些点双中的任意原图顶点，都可以出现在某条 $s \to f$ 的简单路径上，因此都可以作为 $c$。

所以固定 $s,f$ 后，问题变成：求圆方树上 $s\to f$ 路径经过的所有点双，其原图顶点并集大小，再去掉起点 $s$ 与终点 $f$。

但是这样会有一个麻烦的点，相邻点双共享的割点会被重复计算，假设路径形如：s - B1 - c1 - B2 - c2 - ... - Bk - f。

其中 $B_{i}$ 是方点，siz[Bi]表示这个点双内包含的原图顶点数，所以我们可以给原图圆点赋值 $-1$，这样刚好就能抵消重复计算。

由此，问题真正转化为：在一棵圆方树上，只允许圆点作为 $s, f$，求所有有序点对 $(s, f)$ 的点权路径和。

不过若是直接枚举点对还是 $\mathcal{O}(n^{2})$，所以换一个视角统计贡献：如果有 cnt[u] 个有序点对 $(s, f)$ 的路径经过 $u$，那么节点 $u$ 对答案的贡献就是 w[u] * cnt[u]。

对每个圆方树节点，统计删去它后各方向中包含多少个原图点，由此计算多少有序原图端点对的路径经过该节点，再乘上节点权值累加。

摘要

本题关键在于：点双之间会共享割点，圆方树必须一边把点双变成方点，一边保留所有原图圆点；理解这一层以后，问题才变成树上路径权值统计。

▶

P4630

struct Edge { int id, v; };
vector<Edge> adj[maxn];
vector<int> comp[maxn];
vector<int> tree[maxn << 1];

int dfn[maxn], low[maxn], timer;
int stk[maxn], top;

bool cut[maxn];
int vcnt;

void add_edge( int u, int v, int id ) {
    adj[u].push_back({ id, v });
    adj[v].push_back({ id, u });
}

void tarjan( int u, int in_edge ) {
    dfn[u] = low[u] = ++ timer;
    stk[++ top] = u;
    int child = 0;
    for( auto [id, v] : adj[u] ) {
        if( !dfn[v] ) {
            ++ child;
            tarjan( v, id );
            low[u] = min( low[u], low[v] );
            if( low[v] >= dfn[u] ) {
                if( in_edge || child >= 2 ) {
                    cut[u] = true;
                }
                ++ vcnt;
                comp[vcnt].push_back( u );
                int x;
                do {
                    x = stk[top --];
                    comp[vcnt].push_back( x );
                } while( x != v );
            }
        } else if( id != in_edge ) {
            low[u] = min( low[u], dfn[v] );
        }
    }

    if( !in_edge && child == 0 ) {
        comp[++ vcnt].push_back( u );
        -- top;
    }
}

int n;
ll siz[maxn << 1];
ll weight[maxn << 1];
bool vis[maxn];
ll ans;

void dfs_siz( int u, int p ) {
    vis[u] = true;
    siz[u] = ( u <= n );
    for( int v : tree[u] ) {
        if( v == p ) continue;
        dfs_siz( v, u );
        siz[u] += siz[v];
    }
}

void dfs_calc( int u, int p, ll all ) {
    ll cnt = 0;
    ll pre = all - siz[u];
    for( int v : tree[u] ) {
        if( v == p ) continue;
        cnt += 2ll * pre * siz[v];
        pre += siz[v];
        dfs_calc( v, u, all );
    }
    if( u <= n ) cnt += 2ll * ( all - 1 );
    ans += weight[u] * cnt;
}

void solve( ) {
    n = read( );
    int m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        add_edge( u, v, i );
    }

    for( int i = 1; i <= n; ++ i ) {
        if( !dfn[i] ) top = 0, tarjan( i, 0 );
    }
    
    int tot = n + vcnt;
    for( int i = 1; i <= tot; ++ i ) {
        tree[i].clear( );
    }
    for( int id = 1; id <= vcnt; ++ id ) {
        int block = n + id;
        for( int u : comp[id] ) {
            tree[block].push_back( u );
            tree[u].push_back( block );
        }
    }

    for( int u = 1; u <= n; ++ u ) {
        weight[u] = -1;
    }

    for( int id = 1; id <= vcnt; ++ id ) {
        weight[n + id] = comp[id].size( );
    }

    for( int i = 1; i <= n; ++ i ) {
        if( vis[i] ) continue;
        dfs_siz( i, 0 );
        dfs_calc( i, 0, siz[i] );
    }

    cout << ans << '\n';
}