题目传送门：https://www.luogu.com.cn/problem/P3379
倍增LCA模板：
1 #include2 #include ; i++) { 27 fa[x][i] = fa[fa[x][i - 1]][i - 1]; 28 } 29 for (int i = 0; i < G[x].size(); i++) { 30 if (G[x][i] != pre) dfs(G[x][i], x); 31 } 32 33 } 34 35 int lca(int x, int y) { 36 37 if (dep[x] < dep[y]) swap(x, y); 38 for (int i = 30; i >= 0; i--) { 39 if ((1 << i) fa[x][i]; 40 } 41 if (x == y) return x; 42 for (int i = 30; i >= 0; i--) { 43 if (fa[x][i] != fa[y][i]) { 44 x = fa[x][i]; 45 y = fa[y][i]; 46 } 47 } 48 49 return fa[x][0]; 50 } 51 52 int main() { 53 54 int n, m, s; 55 cin >> n >> m >> s; 56 for (int i = 1; i < n; i++) { 57 int u, v; 58 cin >> u >> v; 59 G[u].push_back(v); 60 G[v].push_back(u); 61 } 62 dfs(s, 0); 63 for (; m; --m) { 64 int x, y; 65 cin >> x >> y; 66 cout << lca(x, y) << "\n"; 67 } 68 69 return 0; 70 }3 #include 4 #include 5 #include
永远热爱，永远向着光。
Original: https://www.cnblogs.com/wabi/p/16520311.html
Author: Kyrizer_W
Title: P3379 【模板】最近公共祖先（LCA）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/587882/
转载文章受原作者版权保护。转载请注明原作者出处！