P4320 道路相遇

链接：https://www.luogu.com.cn/problem/P4320

圆方树基础题

实际上就是问给定起点和终点的一条路径上的割点数量。那么建立好圆方树以后，割点的相邻两个点一定是方点，圆点到圆点之间的距离一定是偶数，于是可以知道一条路径中的割点数量= 路径总长度/2 向下取整。那么这道题就转化成建立圆方树之后求路径长度即可。

注意几个细节：因为题目要求起点和终点也要算进去，不要忘了+2.
代码中求LCA用的是树剖。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define mp make_pair
#define ull unsigned long long
#define all(x) x.begin(), x.end()
//__builtin_count()
typedef array<int,2> pr;
const unsigned int mask =  (chrono::steady_clock::now().time_since_epoch().count());
inline int gcd(int a, int b){return b == 0 ? a : gcd(b, a % b);}//gcd(a,b)=gcd(a,b-a)(b>a);
inline int lcm(int a, int b){return a / gcd(a, b) * b;}//lcm(n,m)=n*m/gcd(n,m)
const ll mod = 998244353;
const int inv2 = (mod+1)/2;
#define lson rt<<1
#define rson rt<<1|1
int addmod(int &x, int y) {x = (x + y >= mod ? x + y - mod : x + y);return 1;}
ll qpow(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll inv(int x){return qpow(x,mod-2);}
inline void read(__int128 &x)
{
    char c; while(!((c=getchar())>='0'&&c<='9'));
    x=c-'0';
    while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
int o[200010],on;
inline void output(__int128 x)
{
    on=0;
    while(x) o[++on]=x%10,x/=10;
    for(int i=on;i>=1;i--) cout<<o[i];
}
const int maxn = 1000010;
vector<int> vec[maxn],H[maxn];
int n,m;
int dfn[maxn],low[maxn],idx,fa[maxn];
int dep[maxn],siz[maxn],son[maxn],top[maxn];
int tot;
stack<int> st;
void tarjan(int u)
{
    dfn[u]=low[u]=++idx;
    st.push(u);
    for(auto v:vec[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
            if(dfn[u]==low[v])
            {
                tot++;
                while(1)
                {
                    int x=st.top();
                    st.pop();
                    H[tot].push_back(x);
                    fa[x]=tot;
                    if(x==v) break;
                }
                H[u].push_back(tot);
                fa[tot]=u;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
void dfs1(int now)
{
    dep[now]=dep[fa[now]]+1;
    siz[now]=1;
    int maxx=-1;
    for(auto to:H[now])
    {
        if(to!=fa[now])
        {
            fa[to]=now;
            dfs1(to);
            siz[now]+=siz[to];
            if(siz[to]>maxx)
            {
                maxx=siz[to];
                son[now]=to;
            }
        }
    }
}
void dfs2(int now,int t)
{
    top[now]=t;
    if(!son[now]) return ;
    dfs2(son[now],t);
    for(auto to:H[now])
    {
        if(to==fa[now]||to==son[now])
        {
            continue;
        }
        dfs2(to,to);
    }
}
int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        {
            swap(x,y);
        }
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
    {
        swap(x,y);
    }
    return x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    tot=n;
    // for(int i=1;i<=n;i++)
    // {
    //     if(!dfn[i]) tarjan(i);
    // }//这样写也是可以的
    tarjan(1);
    dfs1(1);
    dfs2(1,1);
    int q;
    cin>>q;
    while(q--)
    {
        int u,v;
        cin>>u>>v;
        cout<<(dep[u]+dep[v]-2*dep[lca(u,v)]+2)/2<<'\n';
    }
}