1 #include <algorithm> 2 #include <cstdio> 3 #include <vector> 4  5 #define N 10015 6  7 using namespace std; 8  9 vector<int>vec[N];10 int n,a,b,m,deep[N],dad[N][100];11 12 int LCA(int x,int y)13 {14     if(deep[x]>deep[y]) swap(x,y);15     for(int i=20;i>=0;i--)16         if(deep[dad[y][i]]>=deep[x]) y=dad[y][i];17     if(x==y) return x;18     for(int i=20;i>=0;i--)19         if(dad[x][i]!=dad[y][i])20         x=dad[x][i],y=dad[y][i];21     return dad[x][0];22 }23 24 void DFS(int x)25 {26     deep[x]=deep[dad[x][0]]+1;27     for(int i=0;dad[x][i];i++)28         dad[x][i+1]=dad[dad[x][i]][i];29     for(int i=0;i<vec[x].size();i++)30         if(!deep[vec[x][i]]) dad[vec[x][i]][0]=x,DFS(vec[x][i]);31 }32 33 int main()34 {35     scanf("%d",&n);36     for(int i=1;i<n;i++)37     {38         scanf("%d%d",&a,&b);39         vec[a].push_back(b);40         vec[b].push_back(a);41     }42     DFS(1);43     scanf("%d",&m);44     while(m--)45     {46         scanf("%d%d",&a,&b);47         printf("%d\n",LCA(a,b));48     }49     return 0;50 }51 /*52 653 1 254 1 355 4 256 5 257 3 658 559 4 560 2 661 3 662 1 563 4 664 */