【LOJ#10134】dis

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 typedef long long ll;
 5 inline int read() {
 6     int ret=0,f=1;
 7     char c=getchar();
 8     while(c<‘0‘||c>‘9‘) {if(c==‘-‘) f=-1;c=getchar();}
 9     while(c<=‘9‘&&c>=‘0‘) ret=ret*10+c-‘0‘,c=getchar();
10     return ret*f;
11 }
12 using namespace std;
13 int n,m;
14 struct edge {
15     int next,to;
16 }a[100010<<1];
17 int head[100010<<1],num,dis[100010],fa[100010][25],log[100010];
18 inline void add(int from,int to) {
19     a[++num].next=head[from];
20     a[num].to=to;
21     head[from]=num;
22     swap(from,to);
23     a[++num].next=head[from];
24     a[num].to=to;
25     head[from]=num;
26 }
27 void dfs(int now,int f) {
28     dis[now]=dis[f]+1;
29     for(int i=0;i<=20;i++) fa[now][i+1]=fa[fa[now][i]][i];
30     for(int i=head[now];i;i=a[i].next) {
31         int v=a[i].to;
32         if(v==f) continue ;
33         fa[v][0]=now;
34         dfs(v,now);
35     }
36 }
37 int lca(int x,int y) {
38     if(dis[x]<dis[y]) swap(x,y);
39     for(int i=20;i>=0;i--) {
40         if(dis[fa[x][i]]>=dis[y]) x=fa[x][i];
41         if(x==y) return x;
42     }
43     for(int i=20;i>=0;i--)
44         if(fa[x][i]!=fa[y][i]) {
45             x=fa[x][i];
46             y=fa[y][i];
47         }
48     return fa[x][0];
49 }
50 int main() {
51     n=read();
52     for(int i=1,x,y;i<n;i++) {
53         x=read(); y=read();
54         add(x,y);
55     }
56     log[0]=-1;
57     for(int i=1;i<=20;i++) log[i]=log[i<<1]+1;
58     dfs(1,0);
59     m=read();
60     while(m--) {
61         int x=read(),y=read();
62         printf("%d\n",dis[x]+dis[y]-dis[lca(x,y)]*2);
63     }
64     return 0;
65 }