点的距离
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn=2e5; int x,y,dep[maxn],f[maxn][25],n; int nxt[maxn<<1],first[maxn<<1],go[maxn<<1],tot; void add(int u,int v) { nxt[++tot]=first[u],first[u]=tot,go[tot]=v; nxt[++tot]=first[v],first[v]=tot,go[tot]=u; } void dfs(int u,int father) { dep[u]=dep[father]+1; for(int i=0;i<20;i++) f[u][i+1]=f[f[u][i]][i]; for(int e=first[u];e;e=nxt[e]) { int v=go[e]; if(v==father) continue; f[v][0]=u; dfs(v,u); } } 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]; } int dis(int x,int y) { return dep[x]+dep[y]-2*dep[LCA(x,y)]; } int main() { tot=0; memset(nxt,-1,sizeof nxt); memset(dep,0,sizeof dep); memset(first,0,sizeof first); scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y); } int m; dfs(1,0); scanf("%d",&m); while(m--) { scanf("%d%d",&x,&y); printf("%d\n",dis(x,y)); } return 0; }