每日一题 小A的最短路 (LCA)

一.题意

给出一棵树，其中有一对 可视为距离 0，
q 次询问， 询问两点之间的距离。

二.题解

LCA 模板题。
单纯求树上两点距离的话:
考虑其中有一对特殊点视为距离 0，所以还要考虑: 和
所以答案为:

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){
   ll s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

const int manx=3e5+5;
const int N=5e2+5;
const int mod=1e9+7;

ll n,q,f[18][manx],h[manx];
vector<ll>g[manx];
void dfs(ll u){
    for(auto v: g[u]){
        if(v==f[0][u]) continue;
        f[0][v]=u;
        h[v]=h[u]+1;
        dfs(v);
    }
}
ll lca(int x, int y){
    if(h[x]<h[y]) swap(x,y);
    for(int i=17;i>=0;i--){
        if( (h[x]-h[y])>>i)
            x=f[i][x];
    }
    if(x==y) return x;
    for(int i=17;i>=0;i--){
        if(f[i][x]!=f[i][y])
            x=f[i][x],y=f[i][y];
    }
    return f[0][x];
}
ll dis(int x,int y){
    return h[x]+h[y]-h[lca(x,y)]*2;
}
int main(){
    n=read();
    for(int i=1;i<n;i++){
        ll u=read(),v=read();
        g[u].pb(v); g[v].pb(u);
    }
    dfs(1);
    for(int i=1;i<=17;i++)
        for(int j=1;j<=n;j++)
            f[i][j]=f[i-1][ f[i-1][j] ];
    ll x=read(),y=read();
    q=read();
    while(q--){
        ll u=read(),v=read();
        ll d1=dis(u,v);
        ll d2=dis(u,x)+dis(y,v);
        ll d3=dis(u,y)+dis(x,v);
        d1=min(d1,d2); d1=min(d1,d3);
        printf("%lld\n",d1);
    }
    return 0;
}