1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=1000001; 7 int n,m,root; 8 struct node 9 {10     int u;11     int v;12     int next;13 }edge[MAXN];14 int num=1;15 int head[MAXN];16 int deep[MAXN];17 int f[MAXN][20];18 void edge_add(int x,int y)19 {20     edge[num].u=x;21     edge[num].v=y;22     edge[num].next=head[x];23     head[x]=num++;24 }25 void build_tree(int p)26 {27     for(int i=head[p];i!=-1;i=edge[i].next)// 遍历与p节点相邻的节点 28     {29         int will=edge[i].v;30         if(deep[will]==0)// 如果点will没有被访问过的话 31         {32             deep[will]=deep[p]+1;// 则点will的深度==p的深度+1 33             f[will][0]=p;// will点向上跳2^0的节点是p 34             build_tree(will);//继续初始化will节点 35         }36     }37 }38 void initialize_step()39 {40     for(int i=1;i<=19;i++)41         for(int j=1;j<=n;j++)42             f[j][i]=f[f[j][i-1]][i-1];43     // 第j个节点，向上跳i能到达的节点就是 跳到i-1处再向上跳i-1能到达的节点44     // 因为倍增是以次方的形式增加的 45 }46 int LCA(int x,int y)47 {48     if(deep[x]<deep[y])swap(x,y);// 如果说节点x的深度比节点y的深度小的话，就交换他俩的位置，让x<y 49     for(int i=19;i>=0;i--)// 因为跳的步数越小越好，所以从最大的值开始跳50     {51         if(deep[f[x][i]]>=deep[y])// 如果跳完i步之后x还在y下方的话 ，这里必须加等于号 52         x=f[x][i];// 就更新x的值，继续跳53     }54     if(x==y)return y;//判断一下，如果x和y在同一条线上，就直接返回x的值 ，y也可以 55     56     for(int i=19;i>=0;i--)//再让x和y一起向上跳57     if(f[x][i]!=f[y][i])58     x=f[x][i],y=f[y][i];// 如果他们跳完之后的祖先不相等的话,就继续跳 59     return f[x][0];//按这样跳下去，一定会跳到只要再跳一步就能找到最近公共祖先的位置！ 60 }61 void read(int & x)62 {63     char c=getchar();x=0;64     while(c<‘0‘||c>‘9‘)c=getchar();65     while(c>=‘0‘&&c<=‘9‘)x=x*10+c-48,c=getchar();// 读入优化，必须要有！ 66 }67 int main()68 {69     //scanf("%d%d%d",&n,&m,&root);70     read(n);read(m);read(root);71     for(int i=1;i<=n;i++)head[i]=-1;72     for(int i=1;i<=n-1;i++)73     {74         int x,y;75         //scanf("%d%d",&x,&y);76         read(x);read(y);77         edge_add(x,y);78         edge_add(y,x);79     }80     deep[root]=1;//将根节点的深度设为1 81     build_tree(root);// 建立起一棵树 82     initialize_step();// 初始化向上跳的距离 83     for(int i=1;i<=m;i++)84     {85         int x,y;86         //scanf("%d%d",&x,&y);87         read(x);read(y);// 求x与y的最近公共祖先88         printf("%d\n",LCA(x,y));// ans 89     }90     return 0;91 }