[ACWing397] 逃不掉的路(边双连通分量+树上距离)

由于数论实在是太难了 于是乎转战图论了呜呜呜 数学就交给pym聚聚扒
由于是必须经过的边，所以在同一个边双连通分量中两点之间至少存在两条不重边的道路可以到达彼此。所以直接边双缩点，发现答案就是缩点之后的树中两点的距离（其实也就是割边的数量
所以直接边双缩点然后lca求树上两点距离即可
（（没想到这题居然1A 爷青结

#include<bits/stdc++.h>
const int maxn = 1e5+10;
using namespace std;
struct node{
    int to;
    node *next;
}*con[maxn],*con1[maxn];
map<int, int> ge[maxn];
void addedge(node**a, int x, int y){
    node*p = new node;
    p->to = y;
    p->next = a[x];
    a[x] = p;
}
int dfn[maxn],low[maxn];
int cnt;
void dfs(int v, int fa){
    int child = 0;
    dfn[v] = low[v] =++cnt;
    for(node*p = con[v];p;p = p->next)
    if(!dfn[p->to]){
        child++;
        dfs(p->to, v);
        low[v] = min(low[v], low[p->to]);
        if(low[p->to]>dfn[v]) ge[v][p->to] = ge[p->to][v] = 1;
    }else if(p->to != fa) low[v] = min(low[v], dfn[p->to]);
}
int n,m;
int c[maxn],cnum;
void build_graph(){
    scanf("%d%d",&n,&m);
    int x, y;
    for(int i = 1;i <= m; ++i){
        scanf("%d%d", &x, &y);
        addedge(con, x, y);
        addedge(con, y, x);
    }
}
void dfs2(int v){
    c[v]=cnum;
    for(node*p=con[v];p;p=p->next)
        if(ge[v][p->to]) continue;
            else if(!c[p->to]) dfs2(p->to);
}
void build_new_graph(){
    for(int i = 1; i <= n; ++i)
        if(!c[i])
            ++cnum,dfs2(i);
    for(int i = 1; i <= n; ++i)
        for(node*p = con[i]; p; p = p->next)
            if(c[i] != c[p->to])
                addedge(con1, c[i], c[p->to]);
}
int fa[maxn][18];
int de[maxn];
int lca(int x, int y){
    if(de[x] < de[y]) swap(x, y);
    for(int i = 17; i >= 0; i--)
    if(de[fa[x][i]]>=de[y])
        x = fa[x][i];
    for(int i = 17; i >= 0; i--)
        if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return x == y? x:fa[x][0];
}
void dfs3(int v, int f){
    fa[v][0]=f;
    for(node*p = con1[v]; p; p = p->next)
        if(p->to != f)
            de[p->to] = de[v] + 1,dfs3(p->to, v);
}
void init(){
    dfs3(1, 1);
    for(int i = 1; i<=17; ++i)
        for(int j = 1; j <= n; ++j)
            fa[j][i] = fa[fa[j][i-1]][i-1];
}
void solve(){
    int _lca,q,x,y;
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &x, &y);
        x = c[x]; y = c[y];
        _lca = lca(x ,y);
        printf("%d\n",de[x]-de[_lca]+de[y]-de[_lca]);
    }
}
int main(){
    build_graph();
    for(int i = 1;i <= n; ++i)
        if(!dfn[i]) dfs(i, i);
    build_new_graph();
    init();
    solve();
    return 0;
}