【牛客】 小A的最短路 （LCA）

原题链接

题意：

给定一棵树，除给定的特殊边边权为0外，其余边权均为1。求两点之间的最短距离。n为3e5

思路：

题目是一棵树这个条件有点隐蔽直接进行最短路可能并不可行，考虑树上求两点距离的方法，一般就是LCA。

因为存在特殊边，所以节点a和b之间的距离可能有三种情况，一是考虑不经过特殊边，直接从节点a到节点b；二是考虑经过特殊边，这时候就考虑顺序了，设特殊边的两个端点分别是q,w；要么是a-x-y-b,要么是b-x-y-a；三者取min就好了。

代码：

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
#define I_int ll
#define x first
#define y second
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int inf=0x3f3f3f3f,mod=1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn=3e5+100,maxm=3e6+7;
const double PI = atan(1.0)*4;

vector<int>G[maxn*2];
int n,U,V,m;
int dep[maxn],fa[maxn][20];

void dfs(int u){
    for(int i=1;i<20;i++)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=0;i<G[u].size();i++){
        int j=G[u][i];
        if(fa[u][0]==j) continue;
        dep[j]=dep[u]+1;
        fa[j][0]=u;
        dfs(j);
    }
}

int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    for(int k=15;k>=0;k--)
        if(dep[fa[a][k]]>=dep[b]) a=fa[a][k];///使a,b跳到同一层
    if(a==b) return a;
    for(int k=15;k>=0;k--)
        if(fa[a][k]!=fa[b][k]) a=fa[a][k],b=fa[b][k];
    return fa[a][0];
}

int cul(int u,int v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}

int main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1);
    U=read(),V=read(),m=read();
    while(m--){
        int u=read(),v=read();
        int minn=min(cul(u,v),cul(u,U)+cul(V,v));
        minn=min(minn,cul(u,V)+cul(U,v));
        out(minn);puts("");
    }
    return 0;
}