1
树上倍增
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(dad[x][i]!=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 ",lca(p,q)); 69 } 70 return 0; 71 }
关于书剖的lca// http://blog.csdn.net/wazwaztime/article/details/51416187
1 /*size x为以x为结点的子树的结点的个数 每个结点和它的儿子之间只有一条重边， 2 这个重边连向它的儿子中size最大的那个儿子。 3 如果结点u和它的儿子v之间是一条轻边， 4 那么sizev*2<size u，因为这个儿子一定分不到它爸爸size的一半嘛。 5 top i 记录i结点所在链的链头，如果top u !=top v 说明u v不在一条链上 将 u=dad[u]，重复上述操作； 6 当它们在一条链上时，深度较小的那个点为他们的lca; 7 8 */ 9 10 11 #include<cstdio> 12 #include<vector> 13 14 using namespace std; 15 16 #define N 500005 17 18 vector<int>vec[N]; 19 int n,m,x,y,p,q,t; 20 21 int dad[N],deep[N],top[N],size[N]; 22 23 inline void dfs(int x) 24 { 25 size[x]=1; 26 deep[x]=deep[dad[x]]+1; 27 for(int i=0;i<vec[x].size();i++) 28 { 29 if(dad[x]!=vec[x][i]) 30 { 31 dad[vec[x][i]]=x; 32 dfs(vec[x][i]); 33 size[x]+=size[vec[x][i]]; 34 35 } 36 } 37 } 38 39 inline int read() 40 { 41 int f=1,x=0;char ch; 42 do{ch=getchar();if(ch=='-')f=-1;} 43 while(ch<'0'||ch>'9'); 44 do{x=x*10+ch-'0';ch=getchar();} 45 while(ch>='0'&&ch<='9'); 46 return f*x; 47 } 48 49 inline void dfsl(int x) 50 { 51 int s=0; 52 if(!top[x])top[x]=x; 53 for(int i=0;i<vec[x].size();i++) 54 { 55 if(dad[x]!=vec[x][i]&&size[vec[x][i]]>size[s]) 56 s=vec[x][i]; 57 } 58 if(s) 59 { 60 top[s]=top[x]; 61 dfsl(s); 62 } 63 for(int i=0;i<vec[x].size();i++) 64 { 65 if(dad[x]!=vec[x][i]&&vec[x][i]!=s)dfsl(vec[x][i]); 66 67 } 68 69 } 70 71 inline int lca(int x,int y) 72 { 73 for(;top[x]!=top[y];)//bu zai yi qi 74 { 75 if(deep[top[x]]<deep[top[y]])swap(x,y); 76 77 x=dad[top[x]];//让它变成lt的爸爸 ； 78 79 } 80 if(deep[x]<deep[y])return x; 81 else return y; 82 83 } 84 int main() 85 86 { 87 88 scanf("%d%d%d",&n,&m,&t);//n个点m条边t个访问； 89 for(int i=1;i<n;i++) 90 { 91 x=read();y=read(); 92 vec[x].push_back(y); 93 vec[y].push_back(x); 94 95 } 96 dfs(1);//初始size deep dad 97 dfsl(1);//解剖 98 while(m--) 99 { 100 p=read(); 101 q=read(); 102 103 printf("%d ",lca(p,q)); 104 } 105 106 return 0; 107 }