洛谷 P3379 【模板】最近公共祖先（LCA）

题目传送门

解题思路：

自己懒得写，看一位大佬写的不错（三种方法）。//任意门

AC代码：

倍增做法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int n,m,s,head[500002],tot,d[500002],p[500002][21];
 8 struct kkk {
 9     int v,next;
10 }e[1000002];
11 
12 void add(int u,int v) {
13     e[tot].v = v;
14     e[tot].next = head[u];
15     head[u] = tot++;
16 }
17 
18 void dfs(int u,int fa) {
19     d[u] = d[fa] + 1;
20     p[u][0] = fa;
21     for(int i = 1;(1 << i) <= d[u]; i++)
22         p[u][i] = p[p[u][i-1]][i-1];
23     for(int i = head[u];i != -1;i = e[i].next) {
24         int v = e[i].v;
25         if(v != fa)
26             dfs(v,u);
27     }
28 }
29 
30 int lca(int a,int b) {
31     if(d[a] > d[b])
32         swap(a,b);
33     for(int i = 20;i >= 0; i--)
34         if(d[a] <= d[b] - (1 << i))
35             b = p[b][i];
36     if(a == b) return a;
37     for(int i = 20;i >= 0; i--) {
38         if(p[a][i] == p[b][i])
39             continue;
40         else
41             a = p[a][i],b = p[b][i];
42     }
43     return p[a][0];
44 }
45 
46 int main() {
47     memset(head,-1,sizeof(head));
48     int a,b;
49     scanf("%d%d%d",&n,&m,&s);
50     for(int i = 1;i < n; i++) {
51         scanf("%d%d",&a,&b);
52         add(a,b);
53         add(b,a);
54     }
55     dfs(s,0);
56     for(int i = 1;i <= m; i++) {
57         scanf("%d%d",&a,&b);
58         printf("%d
",lca(a,b));
59     }
60     return 0;
61 }