树上倍增求解LCA 模板

//详解见https://www.cnblogs.com/zwfymqz/p/7795299.html

//博主：自为风月马前卒 https://www.cnblogs.com/zwfymqz/

// 洛谷 P3379 最近公共祖先链接https://www.luogu.org/problem/P3379

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int MAXN = 5e5+10;
 9 
10 struct node {// 链式向前星  具体原理见博客https://blog.csdn.net/acdreamers/article/details/16902023

11 int v, next; 12 } edge[2*MAXN]; 13 14 int head[2*MAXN];

15 int num = 1;
16 inline void add_edge(int x, int y) {
17     edge[num].v = y;
18     edge[num].next = head[x];
19     head[x] = num++;
20 }
21 
22 int f[MAXN][21];
23 int deep[MAXN];
24 int n, m, root;
25 void dfs(int cur) {
26     for(int i = head[cur]; i != -1; i = edge[i].next) {
27         if(!deep[edge[i].v]) {
28             deep[edge[i].v] = deep[cur] + 1;
29             f[edge[i].v][0] = cur;
30             dfs(edge[i].v);
31         }
32     }
33 }
34 
35 void PRE() {
36     for(int j = 1; j <= 19; ++j) {
37         for(int i = 1; i <= n; ++i) {
38             f[i][j] = f[f[i][j-1]][j-1];
39         }
40     }
41 }
42 
43 int LCA(int x, int y) {
44     if(deep[x] < deep[y]) swap(x, y);
45     for(int i = 19; i >= 0; --i) {
46         if(deep[f[x][i]] >= deep[y]) {
47             x = f[x][i];
48         }
49     }
50     if(x == y) return x;
51     for(int i = 19; i >= 0; --i) {
52         if(f[x][i] != f[y][i]) {
53             x = f[x][i];
54             y = f[y][i];
55         }
56     }
57     return f[x][0];
58 }
59 
60 int main() {
61     memset(head, -1, sizeof(head));
62     scanf("%d%d%d", &n, &m, &root);
63     int x, y;
64     for(int i = 0; i != n-1; ++i) {
65         scanf("%d%d", &x, &y);
66         add_edge(x, y);
67         add_edge(y, x);
68     }
69     deep[root] = 1;
70     printf("%d
", head[root]);
71     dfs(root);
72     PRE();
73     for(int i = 0; i != n; ++i) {
74         scanf("%d%d", &x, &y);
75         printf("%d
", LCA(x, y));
76     }
77     return 0;
78 }