LCA：最近公共祖先问题

解决方法：

       1. 采用链式前行星存图，可以优化空间占用和遍历速度

       2. Tarjan离线可以一次性处理所有的请求，时间复杂度为O(n+q)

 

下面简单介绍下Tarjan离线求LCA：

      首先dfs遍历树，当某个结点左右子树都遍历完成后，处理所有与它有关的请求，然后将其利用并查集合并到父结点上。详见图解、

 

（1）

     

(2)

 

(3)

 

(4)

代码：

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<stack>
  8 #include<deque>
  9 #include<map>
 10 #include<iostream>
 11 using namespace std;
 12 typedef long long  LL;
 13 const double pi=acos(-1.0);
 14 const double e=exp(1);
 15 const int N = 10100;
 16 
 17 #define lson i << 1, l, m
 18 #define rson i << 1 | 1, m + 1, r
 19 int cnt,ans;
 20 int a,b,n;
 21 int root;
 22 int head[N];    //指向结点i的第一条边
 23 int is_root[N]; 
 24 int father[N];  // 并查集的boss结点
 25 int vis[N];
 26 
 27 struct edge
 28 {
 29     int to;
 30     int next;
 31 } edge[N];
 32 
 33 int seek(int ss)
 34 {
 35     int mid;
 36     int head = ss;
 37     while(ss != father[ss])
 38         ss = father[ss];
 39 
 40     while(head != ss)
 41     {
 42         mid = father[head];
 43         father[head] = ss;
 44         head = mid;
 45     }
 46     return ss;
 47 }
 48 
 49 void join(int xx, int yy)
 50 {
 51     int one = seek(xx);
 52     int two = seek(yy);
 53     if(one != two)
 54         father[two] = one;  //注意把谁变成谁的上级
 55 }
 56 
 57 void add(int x, int y)
 58 {
 59     edge[cnt].to = y;
 60     edge[cnt].next = head[x];
 61     head[x] = cnt++;
 62 }
 63 
 64 void init()
 65 {
 66     int i, p, j;
 67     int x, y;
 68     cnt = 0;
 69     memset(head, -1, sizeof(head));
 70     memset(is_root, 0, sizeof(is_root));
 71     memset(vis, 0, sizeof(vis));
 72     scanf("%d", &n);
 73     for(i = 0; i <= n; i++) //并查集预处理
 74         father[i] = i;
 75     for(i = 1; i < n; i++)
 76     {
 77         scanf("%d%d", &x, &y);
 78         add(x, y);            //加边
 79         is_root[y] = 1;       
 80     }
 81     for(i = 1; i <= n; i++)
 82         if(is_root[i] == 0)
 83             root = i;
 84 }
 85 
 86 void LCA(int u)
 87 {
 88     int i, p, j;
 89     for(i = head[u]; i != -1; i = edge[i].next)
 90     {
 91         int v = edge[i].to;
 92         LCA(v);
 93         join(u, v);
 94         vis[v] = 1;
 95     }
 96 
 97     if(u == a && vis[b] == 1)
 98         ans = seek(b);
 99     if(u == b && vis[a] == 1)
100         ans = seek(a);
101 
102     return ;
103 }
104 
105 void solve()
106 {
107     scanf("%d%d", &a, &b);
108     LCA(root);
109 }
110 
111 int main()
112 {
113     int t, m, i, p, j;
114     scanf("%d", &t);
115     for(i = 1; i <= t; i++)
116     {
117         init();  // 链式前向星建图
118         solve(); // Tarjan求LCA
119 
120         printf("%d\n", ans);
121     }
122     return 0;
123 }