1 //lca   倍增  2 /*倍增法 3  4 首先如果两个点的深度如果不同， 5 将深度较大的点跳到与深度较小的点一样的深度， 6 再同时向上跳，首次相遇时即为最近公共祖先。 7 */ 8 #include<cstdio> 9 #include<vector>10 11 using namespace std;12 13 const int N=10015;14 15 vector<int>vec[N];16 int n,m,t,p,q;17 18 int dad[N][N],deep[N];19 20 void dfs(int x)21 {22     deep[x]=deep[dad[x][0]]+1;23     for(int i=0;dad[x][i];i++)24     {25         dad[x][i+1]=dad[dad[x][i]][i];//滚动赋值，如果存在节点x的第2^i的祖先那么节点x的第2^（i+1）个祖先=节点x的2^i的祖先再往前走2^i个祖先26     }27     for(int i=0;i<vec[x].size();i++)28     if(!deep[vec[x][i]])29     {30         dad[vec[x][i]][0]=x;31         dfs(vec[x][i]);32     }33 }34 35 int lca(int x,int y)36 {37     if(deep[x]>deep[y])swap(x,y);38     for(int i=20;i>=0;i--)39     {40         if(deep[dad[y][i]]>=deep[x])y=dad[y][i];41     }//自己跳 42     if(x==y)return x;43     44     for(int i=20;i>=0;i--)45     if(deep[dad[x][i]]!=deep[dad[y][i]])46     {47         x=dad[x][i];48         y=dad[y][i];49     }//一起跳 50     return dad[x][0]; 51 }52 53 int main()54 {55     scanf("%d%d%d",&n,&m,&t);//n个点，m条边，t个访问56     int x,y;57     58     for(int i=1;i<=m;i++)59     {60         scanf("%d%d",&x,&y);61          vec[x].push_back(y);62          vec[y].push_back(y);63     }64     dfs(1);65     while(t--)66     {67         scanf("%d%d",&p,&q);68         printf("%d\n",lca(p,q));69     }70     return 0;71 }