CF1763F Edge Queries

· · 题解

首先题目给的条件没有用，对于一般无向连通图，以下做法仍然成立。

以下称点双连通分量为点双，边双连通分量为边双。

解法一：建点双圆方树，对于两点之间的树上路径中的方点，如果其对应点双有大于等于 2 条边，则这个点双里随便删边仍然连通，否则（即一边连两点的点双情况）删掉之后不连通。

所以圆点和只有一条边的方点点权为 0，其它方点点权为对应点双内边数，求树上路径点权和。

解法二：建边双圆方树（应该可以这么称呼），方点点权为对应边双内的边数，圆点点权为 0，求路径上点权和（没写过）。

具体实现上，对于计算一个边双或者点双内的边数，可以考虑记录每个点双（边双）内的点，然后遍历每个点双（边双），将其中的点标记，然后枚举一端在这个点双（边双）中的边，如果另一端也有标记，则这条边是这个点双（边双）中的，最后把标记取消，遍历下一个点双（边双）。

其次，因为是个静态问题，所以求树上路径点权和可以用树上差分，求最近公共祖先的话因人而异，我写的是树剖。

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, m, q;
int dfn[N], low[N], num, st[N], t, cnt, a[N], s[N];
vector<int> e[N], p[N], g[N];
int d[N], son[N], f[N], top[N], siz[N];
bool flag[N];
void dfs(int x, int fa) {
    dfn[x] = low[x] = ++num; st[++t] = x;
    for (int i = 0; i < e[x].size(); i++) {
        int y = e[x][i];
        if (!dfn[y]) {
            dfs(y, x); low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                cnt++;
                while (t) {
                    int z = st[t--];
                    g[z].push_back(cnt); g[cnt].push_back(z); p[cnt].push_back(z);
                    if (z == y) break;
                }
                g[x].push_back(cnt); g[cnt].push_back(x); p[cnt].push_back(x);
            }
        } else if (y != fa) low[x] = min(low[x], dfn[y]);
    }
}
void dfs1(int x) {
    d[x] = d[f[x]] + 1; siz[x] = 1;
    if (x == 1) s[x] = a[x];
    for (int i = 0; i < g[x].size(); i++) { 
        int y = g[x][i];
        if (y != f[x]) {
            f[y] = x; s[y] = s[x] + a[y]; dfs1(y); siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) son[x] = y;
        }
    }
}
void dfs2(int x, int pa) {
    top[x] = pa;
    if (son[x]) dfs2(son[x], pa);
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (y != f[x] && y != son[x]) dfs2(y, y);
    }
}
int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    if (d[x] > d[y]) swap(x, y);
    return x;
}
int main() {
    cin >> n >> m; cnt = n;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y; e[x].push_back(y); e[y].push_back(x);
    }
    dfs(1, 0);
    for (int i = n + 1; i <= cnt; i++) {
        for (int j = 0; j < p[i].size(); j++) {
            int x = p[i][j];
            flag[x] = 1;
        }
        for (int j = 0; j < p[i].size(); j++) {
            int x = p[i][j];
            for (int k = 0; k < e[x].size(); k++) {
                int y = e[x][k];
                if (flag[y]) a[i]++;
            }
        }
        for (int j = 0; j < p[i].size(); j++) {
            int x = p[i][j];
            flag[x] = 0;
        }
        a[i] /= 2;
        if (a[i] == 1) a[i] = 0;
    }
    dfs1(1); dfs2(1, 1);
    cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        int LCA = lca(x, y), res = s[x] + s[y] - s[LCA] * 2;
        if (LCA > n) res += a[LCA];
        cout << res << endl;
    }
    return 0;
}