題目同上篇，最近公共祖先。

因?yàn)闆]有清零tot，RE了好多次TAT

一定要初始化啊！！

1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<iostream> 5 using namespace std; 6 int root,head[10010]; 7 int next[10010],to[10010],tot; 8 int deep[10010],n; 9 int p[10010][16]; 10 int deg[10010]; 11 inline void bfs(int root) { 12 queue<int> Q; 13 p[root][0]=root; deep[root]=0; 14 Q.push(root); 15 while(!Q.empty()) { 16 int u=Q.front(); Q.pop(); 17 for(int i=1;i<15;i++) 18 p[u][i]=p[p[u][i-1]][i-1]; 19 for(int i=head[u];i!=-1;i=next[i]) { 20 int v=to[i]; 21 deep[v]=deep[u]+1; p[v][0]=u; 22 Q.push(v); 23 } 24 } 25 } 26 inline int LCA(int x,int y) { 27 if(deep[x]<deep[y]) {int t=x;x=y;y=t;} 28 for(int i=0;i<15;i++) 29 if((deep[x]-deep[y]) & (1<<i)) x=p[x][i]; 30 if(x==y) return x; 31 for(int i=14;i>=0;i--) 32 if(p[x][i]!=p[y][i]) 33 x=p[x][i],y=p[y][i]; 34 return p[x][0]; 35 } 36 int main() { 37 int T; 38 scanf("%d",&T); 39 while(T--) { 40 tot=0; 41 memset(head,-1,sizeof(head)); memset(deg,0,sizeof(deg)); 42 scanf("%d",&n); 43 for (int i=1;i<=n-1;++i) { 44 int u,v; 45 scanf("%d%d",&u,&v); 46 to[tot]=v; 47 next[tot]=head[u]; 48 head[u]=tot++; 49 deg[v]=1; 50 } 51 for (int i=1;i<=n;++i) 52 if(! deg[i]) {root=i;break;} 53 bfs(root); 54 int u,v; 55 scanf("%d%d",&u,&v); 56 printf("%d\n",LCA(u,v)); 57 } 58 return 0; 59 } View Code

倍增法簡(jiǎn)介：

deep[i] 表示 i節(jié)點(diǎn)的深度, fa[i,j]表示 i 的 2^j (即2的j次方) 倍祖先，那么fa[i , 0]即為節(jié)點(diǎn)i 的父親，然后就有一個(gè)遞推式子fa[i,j]=fa [fa[i,j-1],j-1]

可以這樣理解：設(shè)tmp = fa [i, j - 1] ，tmp2 = fa [tmp, j - 1 ] ，即tmp 是i 的第2 ^ (j - 1) 倍祖先，tmp2 是tmp 的第2 ^ (j - 1) 倍祖先，

所以tmp2 是i 的第2 ^ (j - 1) + 2 ^ (j - 1) = ?2^ j 倍祖先

注意：這里的“倍”可不能理解為倍數(shù)的意思，而是距離節(jié)點(diǎn)i有多遠(yuǎn)的意思，節(jié)點(diǎn)i的第2 ^ j?倍祖先表示的節(jié)點(diǎn)u滿足deep[ u ] - deep[ i ] = 2 ^ j。

? ? ? ? 這樣子一個(gè)O(NlogN)的預(yù)處理求出每個(gè)節(jié)點(diǎn)的 2^k 的祖先　　
? ? ? ? 然后對(duì)于每一個(gè)詢問(wèn)的點(diǎn)對(duì)a, b的最近公共祖先就是：　

?先判斷是否 d[x]< d[y] ,如果是的話就交換一下(保證 x 的深度大于 y 的深度),?然后把 x 調(diào)到與 y 同深度, 同深度以后再把a(bǔ), b 同時(shí)往上調(diào),調(diào)到有一個(gè)最小的 j?滿足fa [x,j] != fa [y,j] (x,y是在不斷更新的), 最后再把(x,y)往上調(diào)(x=p[x,0], y=p[y,0]) ?,一個(gè)一個(gè)向上調(diào)直到x = y, 這時(shí) x或y 就是他們的最近公共祖先。

?

轉(zhuǎn)載于:https://www.cnblogs.com/TonyNeal/p/poj1330_2.html

總結(jié)

以上是生活随笔為你收集整理的[POJ 1330] Nearest Common Ancestors （倍增法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。