【每日一题】8月3日题目精讲—小A的最短路

#include<bits/stdc++.h>
const int MAX=3e5+50;
using namespace std;
template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-')
            op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op)
        x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0)
        x = -x, putchar('-');
    if(x >= 10)
        write(x / 10);
    putchar('0' + x % 10);
}
struct node
{
    int ch,dis;
};
vector<node> G[MAX*2];
int rdis[MAX];
int father[22][MAX],dep[MAX];
void dfs(int u,int f,int dis)
{
    father[0][u]=f;
    rdis[u]=dis;
    dep[u]=dep[f]+1;
    for(int i=1;i<=21;i++)
    {
        father[i][u]=father[i-1][father[i-1][u]];
    }
    int len=G[u].size();
    for(int i=0;i<len;i++)
    {
        int v=G[u][i].ch;
        if(v==f)continue;
        father[0][v]=u;
        dfs(v,u,dis+G[u][i].dis);
    }
}
void init(int n)
{
    memset(father,0,sizeof(father));
    dep[0]=0;
    dfs(1,0,0);
}
int lca(int u,int v)
{
    if(dep[u]>dep[v]){
        swap(u,v);
    }
    for(int k=0;k<=21;k++)
    {
        if((dep[v]-dep[u])>>k&1){
            v=father[k][v];
        }

    }
    if(u==v)return u;
    for(int k=21;k>=0;k--){
        if(father[k][u]!=father[k][v]){
            u=father[k][u];
            v=father[k][v];
        }
    }
    return father[0][u];

}
int distant(int u,int v)
{
    return rdis[u]+rdis[v]-rdis[lca(u,v)]*2;
}
int main(){
	int n;
	read(n);
	for(int i=1;i<=n-1;i++){
		int a,b;
		read(a);read(b);
		G[a].push_back({b,1});
		G[b].push_back({a,1});
	}
	init(n);
	int x,y;
	read(x);read(y);
	int k;
	read(k);
	for(int i=1;i<=k;i++){
		int c,d;
		read(c);read(d);
		int ans=min(distant(c,x)+distant(d,y),distant(c,y)+distant(d,x));
		ans=min(distant(c,d),ans);
		printf("%d\n",ans);
	}
	return 0;
}