P3379 【模板】最近公共祖先（LCA）
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入输出格式
输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出格式：输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例
输入样例#1：
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
输出样例#1：
4 4 1 4 4
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=10，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例说明：
该树结构如下：
第一次询问：2、4的最近公共祖先，故为4。
第二次询问：3、2的最近公共祖先，故为4。
第三次询问：3、5的最近公共祖先，故为1。
第四次询问：1、2的最近公共祖先，故为4。
第五次询问：4、5的最近公共祖先，故为4。
故输出依次为4、4、1、4、4。
#include <bits/stdc++.h> const int INF = 0x3f3f3f3f; const int MAXN = 500000 + 10; const int MAXE = 500000 + 10; inline void read(int &x) { x = 0;char ch = getchar();char c = ch; while(ch > '9' || ch < '0')c = ch, ch = getchar(); while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar(); if(c == '-')x = -x; } inline void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; } struct Edge{int u,v,next;}edge[MAXE << 1]; int head[MAXN], cnt, n, m, root; void insert(int a,int b){edge[++cnt] = Edge{a, b, head[a]};head[a] = cnt;} int tmp1, tmp2; int b[MAXN]; int p[MAXN][21]; int deep[MAXN]; void dfs(int u, int step) { for(int pos = head[u];pos;pos = edge[pos].next) { int v = edge[pos].v; if(!b[v]) { b[v] = true; deep[v] = step + 1; p[v][0] = u; dfs(v, step + 1); } } } void yuchuli() { b[root] = true; deep[0] = 0; dfs(root, 0); for(int j =1;(1 << j) <= n;j ++) for(int i =1;i <= n;i ++) p[i][j] = p[p[i][j - 1]][j - 1]; } int lca(int va, int vb) { if(deep[va] < deep[vb])swap(va, vb); int M = 0; for(;(1 << M) <= n;M ++); M --; for(int i = M;i >= 0;i --) if(deep[va] - (1 << i) >= deep[vb]) va = p[va][i]; if(va == vb)return va; for(int j = M;j >= 0;j --) { if(p[va][j] != p[vb][j]) { va = p[va][j]; vb = p[vb][j]; } } return p[va][0]; } int main() { read(n);read(m);read(root); for(int i = 1;i < n;i ++) { read(tmp1);read(tmp2); insert(tmp1, tmp2); insert(tmp2, tmp1); } yuchuli(); for(int i = 1;i <= m;i ++) { read(tmp1);read(tmp2); printf("%d ", lca(tmp1, tmp2)); } return 0; }