题目链接：https://www.luogu.org/problemnew/show/P3379
倍增求lca，先存下板子，留个坑以后再填讲解。
in
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
out
4
4
1
4
4
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 const int maxlog = 20; 7 const int maxn = 550000; 8 int n, m, s; 9 int root; 10 int fa[maxn][maxlog]; 11 int deep[maxn]; 12 int head[maxn]; 13 int cnt; 14 struct Edge{ 15 int next; 16 int to; 17 }e[2 * maxn]; 18 void add(int u, int v) 19 { 20 e[cnt].to = v; 21 e[cnt].next = head[u]; 22 head[u] = cnt++; 23 } 24 void dfs(int u, int p, int d) 25 { 26 fa[u][0] = p; 27 deep[u] = d; 28 for(int i = head[u]; i != -1; i = e[i].next) 29 if(e[i].to != p) dfs(e[i].to, u, d+1); 30 } 31 void init() 32 { 33 dfs (root, -1, 0); 34 for(int k = 0; k + 1 < maxlog; k++) 35 { 36 for(int v = 1; v <= n; v++) 37 if(fa[v][k] < 0) fa[v][k+1] = -1; 38 else fa[v][k+1] = fa[fa[v][k]][k]; 39 } 40 } 41 int lca(int u, int v) 42 { 43 if(deep[u] > deep[v]) swap(u, v); 44 for(int k = 0; k < maxlog; k++) 45 { 46 if((deep[v] - deep[u]) >> k & 1) 47 v = fa[v][k]; 48 } 49 if(u == v) return u; 50 for(int k = maxlog - 1; k >= 0; k--) 51 { 52 if(fa[v][k] != fa[u][k]) 53 { 54 u = fa[u][k]; 55 v = fa[v][k]; 56 } 57 } 58 return fa[u][0]; 59 } 60 int main() 61 { 62 memset(head,-1,sizeof(head)); 63 int a,b; 64 scanf("%d%d%d",&n,&m,&root); 65 for(int i = 1; i < n; i++) 66 { 67 scanf("%d%d",&a,&b); 68 add(a,b); 69 add(b,a); 70 } 71 init(); 72 for(int i = 1; i <= m; i++) 73 { 74 int u,v,a; 75 scanf("%d%d",&u,&v); 76 a = lca(u,v); 77 printf("%d ",a); 78 } 79 return 0; 80 } 81 /* 82 in: 83 9 5 1 84 1 2 85 1 3 86 2 5 87 2 4 88 3 6 89 7 9 90 6 7 91 6 8 92 9 8 93 9 5 94 6 5 95 4 3 96 4 5 97 out: 98 6 99 1 100 1 101 1 102 2 103 */
