ConanKIDの小窝

ConanKIDの小窝

CF231E Cactus 题解

posted on 2021-10-18 14:36:01 | under 题解 |

我们发现,通过每个环的合法路径数都有两种。设从 $x$ 到 $y$ 的路径上有 $d$ 个环,那么答案就是 $2^d$。

问题转化为求两点路径间有多少个环。

我们考虑缩边双。由于题目保证图是一个点仙人掌,因此缩完图之后一定是一棵树。此时我们只需要求两点的树上距离即可。

用 LCA 维护一下就可以了。

时间复杂度 $O(n+m+q\log n)$。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
int n, m, q;
int head[100005];
int u[1000005], v[1000005], nxt[1000005];
int low[100005], dfn[100005];
bool cut[1000005];
int dcc[100005], size[100005];
int tot = 1, cnt, lza;
vector<int> a[100005];
int f[100005], dep[100005];
int nmsl[100005], son[100005];
int top[100005];
int len[100005];
void add(int x, int y) {
    tot++;
    u[tot] = x; v[tot] = y; 
    nxt[tot] = head[x]; head[x] = tot;
}
void dfs(int ed, int x) {
    low[x] = dfn[x] = ++cnt;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = v[i];
        if (!dfn[y]) {
            dfs(i, y); low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y]) cut[i] = cut[i ^ 1] = 1;
        } else if (i != (ed ^ 1)) low[x] = min(low[x], dfn[y]);
    }
} 
void dfs2(int x, int cnt) {
    dcc[x] = cnt; size[cnt]++;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = v[i];
        if (dcc[y] || cut[i]) continue;
        dfs2(y, cnt);
    }
}//缩边双
void dfs1(int fa, int x) {
    f[x] = fa; dep[x] = dep[fa] + 1; len[x] = len[fa] + (size[x] > 1); nmsl[x] = 1;
    for (int i = 0; i < a[x].size(); i++) {
        int y = a[x][i];
        if (y == fa) continue;
        dfs1(x, y);
        nmsl[x] += nmsl[y];
        if (son[x] == 0 || nmsl[son[x]] < nmsl[y]) son[x] = y;
    }
}
void dfs3(int x, int t) {
    top[x] = t;
    if (son[x] == 0) return;
    dfs3(son[x], t);
    for (int i = 0; i < a[x].size(); i++) {
        int y = a[x][i];
        if (y == f[x] || y == son[x]) continue;
        dfs3(y, y);
    }
}//预处理树剖求LCA
int ask(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}
ll power(int a, int b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod; b >>= 1;
    }
    return res;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        add(u, v); add(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) dfs(0, i);
    for (int i = 1; i <= n; i++)
        if (!dcc[i])
            dfs2(i, ++lza);
    for (int i = 1; i <= n; i++)
        for (int j = head[i]; j; j = nxt[j]) {
            int x = v[j];
            if (dcc[i] != dcc[x]) a[dcc[i]].push_back(dcc[x]);
        }
    dfs1(0, 1); dfs3(1, 1);
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int x, y; cin >> x >> y; x = dcc[x], y = dcc[y];
        int lca = ask(x, y);
        cout << power(2, len[x] + len[y] - len[lca] * 2 + (size[lca] > 1)) << endl;//由于求的是点权和,因此特判lca这个点
    }
    return 0;
}