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

注释都写在代码里啦

AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <set>
#define bug(x) cout<<#x<<"=="<<x<<endl;
#define lowbit(x) x&(-x)
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;
#define int long long

const int maxn = 500010;
VI son[maxn];
int n, m, k, depth[maxn], fa[maxn][30], a, b, maxd;

void dfs(int x, int pre)//x表示当前dfs节点，pre为其父节点
{
	depth[x] = depth[pre] + 1;//计算x节点深度
	//maxd = max(maxd, depth[x]);
	fa[x][0] = pre;//向上走一步即为其父节点
	for (int i = 1; (1 << i) <= depth[x]; ++i)
		fa[x][i] = fa[fa[x][i - 1]][i - 1];//x向上走2^i步等同于x向上走2^i-1，再走2^i-1;
	for (int i = 0; i < son[x].size(); ++i) {
		if (son[x][i] != pre) dfs(son[x][i], x);//递归处理
	}
}

int up(int x, int d)//计算x向上走d步的节点
{
	int ret = x;//初始化
	for (int i = 26; i >= 0; --i)//考虑d的二进制表示为1的位置，用之前的处理向上跳跃
		if ((1 << i) & d)
			ret = fa[ret][i];
	return ret;
}

int lca(int x, int y) {//计算两个节点之间的lca
	if (depth[x] < depth[y])
		swap(x, y);//保证x深度较大
	x = up(x, depth[x] - depth[y]);
	if (x == y)
		return x;
	for (int i = 26; i >= 0; --i)
		if (fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];//如果跳2^i后不一样就跳上去
	return fa[x][0];
}

signed main()
{
	cin >> n >> m >> k;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		son[a].push_back(b);
		son[b].push_back(a);
	}
	depth[0] = 0;
	dfs(k, 0);//k是根节点
	for (int i = 1; i <= m; ++i) {
		cin >> a >> b;
		cout << lca(a, b) << endl;
	}
	return 0;
}