题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式：
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式：
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
求最近公共祖先的方法：1.树剖，2.倍增，3.RMQ，4.tarjan 1.树剖版 #include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 5; int head[maxn], tot; struct Edge { int u, v, next; }edge[maxn]; int father[maxn], depth[maxn], size[maxn], son[maxn], top[maxn]; int L[maxn], R[maxn], Index; void init() { memset(head, -1, sizeof(head)); tot = 1; } void add(int u, int v) { edge[++tot].u = u; edge[tot].v = v; edge[tot].next = head[u]; head[u] = tot; } void dfs1(int u, int fa) { size[u] = 1; son[u] = 0; father[u] = fa; depth[u] = depth[fa] + 1; int maxson = -1; for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (to == fa) { continue; } dfs1(to, u); size[u] += size[to]; if (size[to] > maxson) { maxson = size[to]; son[u] = to; } } } void dfs2(int u, int topf) { top[u] = topf; L[u] = R[u] = ++Index; if (son[u]) { dfs2(son[u], topf); } for (int i = head[u]; i != -1; i = edge[i].next) { int to = edge[i].v; if (L[to] || to == son[u]) { continue; } dfs2(to, to); } R[u] = Index; } int LCA(int x, int y) { while (top[x] != top[y]) { if (depth[top[x]] < depth[top[y]]) { swap(x, y); } x = father[top[x]]; } if (depth[x] > depth[y]) { return y; } return x; } inline int read() { int ans = 0; char ch = getchar(); while (ch < '0' || ch > '9') { ch = getchar(); } while (ch >= '0' && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); int n, m, s, u, v; n = read(); m = read(); s = read(); for (int i = 1; i <= n - 1; i++) { u = read(); v = read(); add(u, v); add(v, u); } dfs1(s, 0); dfs2(s, s); for (int i = 1; i <= m; i++) { u = read(); v = read(); printf("%d\n", LCA(u, v)); } return 0; }
