POJ 1330 （LCA）

题意：给出一个图，求两个点的最近公共祖先。

sl :水题，贴个模板试试代码。本来是再敲HDU4757的中间发现要用LCA, 操蛋只好用这个题目试试自己写的对不对。下面是个倍增的写法，挺实用的。

好了，继续。。。

1 #include <cstdio>
2 #include <cstring>
3 #include <vector>
4 #include <algorithm>
5 #include <map>
6 #include <cmath>
7 using namespace std;
8 const int MAX = 1e4+10;
9 vector<int> G[MAX];
10 int is_root[MAX];
11 int parent[15][MAX],dep[MAX];
12 int n,m;
13 void add_edge(int from,int to) {
14     G[from].push_back(to);
15     G[to].push_back(from);
16 }
17 void dfs(int u,int pre,int d) {
18     dep[u]=d; parent[0][u]=pre;
19     for(int i=0;i<G[u].size();i++) {
20         int v=G[u][i];
21         if(v!=pre) dfs(v,u,d+1);
22     }
23     return ;
24 }
25 void init() {
26     int x;
27     for(int i=1;i<=n;i++) {
28         if(is_root[i]) {
29             x=i; break;
30         }
31     }
32
33     dfs(x,-1,0);
34     for(int k=0;k<14;k++) {
35         for(int v=1;v<=n;v++) {
36             if(parent[k][v]<0) parent[k+1][v]=-1;
37             else parent[k+1][v]=parent[k][parent[k][v]];
38         }
39     }
40 }
41 int LCA(int u,int v) {
42     if(dep[u]>dep[v]) swap(u,v);
43     for(int k=0;k<15;k++) {
44         if((dep[v]-dep[u])>>k&1) v=parent[k][v];
45     }
46     if(u==v) return u;
47     for(int k=14;k>=0;k--) {
48         if(parent[k][u]!=parent[k][v]) {
49             u=parent[k][u]; v=parent[k][v];
50         }
51     }
52     return parent[0][u];
53 }
54 void CLEAR() {
55     for(int i=0;i<MAX;i++) G[i].clear();
56 }
57 int main() {
58     int cas; int a,b;
59     scanf("%d",&cas);
60     while(cas--) {
61         CLEAR();
62         scanf("%d",&n);
63         memset(is_root,true,sizeof(is_root));
64         for(int i=1;i<=n-1;i++) {
65             scanf("%d %d",&a,&b);
66             add_edge(a,b);
67             is_root[b]=false;
68         }
69         init();
70         scanf("%d %d",&a,&b);
71         int ans=LCA(a,b);
72         printf("%d ",ans);
73     }
74     return 0;
75 }

SB CODE