LCA 模板

LCA

之前没写过 LCA 的相关，现在来总结一下。

求最近公共祖先：

1、 Tarjan 离线，速度很快 n+q

2、 LCA 一般做法复杂度 (n+q) log n

3、RMQ n log n 预处理在线 O(1) 查询

模板题：

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+5;
 4 int n,q,nxt[N*2],to[N*2],hea[N],tot,dep[N],fa[N][22];
 5 inline void add(int x,int y)
 6 {
 7     to[++tot]=y; nxt[tot]=hea[x]; hea[x]=tot;
 8 }
 9 inline int read()
10 {
11     int x=0,f=1; char ch=getchar();
12     while (!isdigit(ch)) f=(ch=='-')?-f:f,ch=getchar();
13     while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
14     return x*f;
15 }
16 inline void dfs(int x,int d,int fat)
17 {
18     for (int i=hea[x]; i; i=nxt[i])
19     {
20         int y=to[i];
21         if (y!=fat && dep[y]==0)
22         {
23             fa[y][0]=x;
24             dep[y]=d+1;
25             dfs(y,d+1,x);
26         }
27     }
28 }
29 inline int LCA(int x,int y)
30 {
31     if (dep[x]<dep[y]) swap(x,y);
32     for (int i=20; ~i; --i)
33       if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
34     for (int i=20; ~i; --i)
35       if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
36     if (x!=y) x=fa[x][0];
37     return x;
38 }
39 int main()
40 {
41     scanf("%d",&n);
42     register int x,y;
43     for (int i=1; i<n; ++i)
44     {
45         x=read(),y=read();        
46         add(x,y); add(y,x);
47     }
48     dfs(1,0,0);
49     for (int i=1; i<=20; ++i)
50       for (int j=1; j<=n; ++j)
51         fa[j][i]=fa[fa[j][i-1]][i-1];
52     scanf("%d",&q);
53     for (int i=1; i<=q; ++i)
54     {
55         x=read(),y=read();
56         printf("%d
",dep[x]+dep[y]-dep[LCA(x,y)]*2);
57     }
58     return 0;
59 }

View Code

有一个注意点：对于幂次循环时，i>=0，这个要注意，=0时也要判断！！！

fighting! fighting! fighting!