POJ 1330 Nearest Common Ancestors (LCA,倍增算法，在线算法)

  1 /* ***********************************************
  2 Author        :kuangbin
  3 Created Time  :2013-9-5 9:45:17
  4 File Name     :F:2013ACM练习专题学习LCAPOJ1330_3.cpp
  5 ************************************************ */
  6 
  7 #include <stdio.h>
  8 #include <string.h>
  9 #include <iostream>
 10 #include <algorithm>
 11 #include <vector>
 12 #include <queue>
 13 #include <set>
 14 #include <map>
 15 #include <string>
 16 #include <math.h>
 17 #include <stdlib.h>
 18 #include <time.h>
 19 using namespace std;
 20 /*
 21  * POJ 1330
 22  * LCA 在线算法
 23  */
 24 const int MAXN = 10010;
 25 const int DEG = 20;
 26 
 27 struct Edge
 28 {
 29     int to,next;
 30 }edge[MAXN*2];
 31 int head[MAXN],tot;
 32 void addedge(int u,int v)
 33 {
 34     edge[tot].to = v;
 35     edge[tot].next = head[u];
 36     head[u] = tot++;
 37 }
 38 void init()
 39 {
 40     tot = 0;
 41     memset(head,-1,sizeof(head));
 42 }
 43 int fa[MAXN][DEG];//fa[i][j]表示结点i的第2^j个祖先
 44 int deg[MAXN];//深度数组
 45 
 46 void BFS(int root)
 47 {
 48     queue<int>que;
 49     deg[root] = 0;
 50     fa[root][0] = root;
 51     que.push(root);
 52     while(!que.empty())
 53     {
 54         int tmp = que.front();
 55         que.pop();
 56         for(int i = 1;i < DEG;i++)
 57             fa[tmp][i] = fa[fa[tmp][i-1]][i-1];
 58         for(int i = head[tmp]; i != -1;i = edge[i].next)
 59         {
 60             int v = edge[i].to;
 61             if(v == fa[tmp][0])continue;
 62             deg[v] = deg[tmp] + 1;
 63             fa[v][0] = tmp;
 64             que.push(v);
 65         }
 66 
 67     }
 68 }
 69 int LCA(int u,int v)
 70 {
 71     if(deg[u] > deg[v])swap(u,v);
 72     int hu = deg[u], hv = deg[v];
 73     int tu = u, tv = v;
 74     for(int det = hv-hu, i = 0; det ;det>>=1, i++)
 75         if(det&1)
 76             tv = fa[tv][i];
 77     if(tu == tv)return tu;
 78     for(int i = DEG-1; i >= 0; i--)
 79     {
 80         if(fa[tu][i] == fa[tv][i])
 81             continue;
 82         tu = fa[tu][i];
 83         tv = fa[tv][i];
 84     }
 85     return fa[tu][0];
 86 }
 87 bool flag[MAXN];
 88 int main()
 89 {
 90     //freopen("in.txt","r",stdin);
 91     //freopen("out.txt","w",stdout);
 92     int T;
 93     int n;
 94     int u,v;
 95     scanf("%d",&T);
 96     while(T--)
 97     {
 98         scanf("%d",&n);
 99         init();
100         memset(flag,false,sizeof(flag));
101         for(int i = 1;i < n;i++)
102         {
103             scanf("%d%d",&u,&v);
104             addedge(u,v);
105             addedge(v,u);
106             flag[v] = true;
107         }
108         int root;
109         for(int i = 1;i <= n;i++)
110             if(!flag[i])
111             {
112                 root = i;
113                 break;
114             }
115         BFS(root);
116         scanf("%d%d",&u,&v);
117         printf("%d
",LCA(u,v));
118     }
119     return 0;
120 }