POJ 1330 Nearest Common Ancestors(LCA、倍増アルゴリズム、オンラインアルゴリズム)
16016 ワード
1 /* ***********************************************
2 Author :kuangbin
3 Created Time :2013-9-5 9:45:17
4 File Name :F:\2013ACM \ \LCA\POJ1330_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 }