#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define endl "\n"
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
const int base=131;
const int mod=1e9+7;
const int N=1e5+9,M=1e6+9;
struct pp
{
int x,y;
}p[N<<1];
int h[N<<1],dep[N],f[N][21];
int n,q,k=0;
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;
for(int i=1;i<=20;i++)
f[x][i]=f[f[x][i-1]][i-1];
for(int i=h[x];~i;i=p[i].x)
{
int y=p[i].y;
if(y==fa)
continue;
f[y][0]=x;
dfs(y,x);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])
swap(x,y);
for(int i=20;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y)
return x;
}
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void add(int x,int y)
{
p[k].x=h[x];
p[k].y=y;
h[x]=k++;
}
void f0(int T)
{
cin>>n;
for(int i=1;i<=n;i++)
h[i]=-1;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,0);
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
cout<<dep[x]+dep[y]-2*dep[lca(x,y)]<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
// cin>>T;
for(int i=1;i<=T;i++)
f0(i);
return 0;
}
标签:const,int,cin,long,add,LCA,define From: https://www.cnblogs.com/2021sgy/p/16811480.html