题目描述

给定一棵 $n$ 个结点的树（结点标号 $1$~$n$ ）以及树中结点的边，结点 s 为树的根。

有 $m$ 次询问，请求出每次询问的两个结点 $x$ 和 $y$ 的最近的公共祖先结点。

输入格式

第 $1$ 行输入 $3$ 个整数 $n$、$m$、$s$（$n \le 500000$，$m \le 500000$，$1 \le s \le n$）；

接下来 $n−1$ 行，每行两个整数 $a$ 和 $b$ ，结点 $a$ 和 $b$ 是父子关系，但不保证 $a$ 是 $b$ 的父，数据保证一定能构成树；

接下来 $m$ 行，每行两个整数 $x$，$y$，表示要求出 $x$ 和 $y$ 结点的公共祖先。

输出格式

输出 $m$ 行，每行一个整数，表示 $m$ 次询问求出的结果。

样例

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

4
4
1
4
4

算法分析

1. 树链剖分的算法是要把树形结构转变成线性结构，也就是把一棵树剖分成若干条线性的链。剖分以后，线性的算法就可以使用了。

2. 一棵树，有 $n$ 个顶点，剖分之后，任何一个顶点 $u$ 到根的路径，不会经过多于 $\log n$ 条重链或者虚边。

3. 引入 dfn ，这是 dfs 遍历树的过程中的遍历序。我们求 $u$ 和 $v$ 的最近公共祖先 $lca$，可以知道 $dfn[lca] \le dfn[u]$ 且 $dfn[lca] \le dfn[v]$。因此，我们可以让 $u$ 和 $v$ 种 $dfn$ 更大的那一个往上跳转，每一次跳转前后，$lca$ 并不改变。一直跳转到 $u$ 和 $v$ 位于同一条重链。这时候，$dfn$ 值小的一个是另外一个的祖先，也是最初 $u$ 和 $v$ 的 $lca$。

完善程序

#include<bits/stdc++.h>
using namespace std;

const int maxn = 500001;

int n,m,s,e_id, dfn_id;
int h[maxn], wc[maxn],Size[maxn], top[maxn], dfn[maxn], fa[maxn];

struct Edge{
	int v,next;
}e[maxn*2];

void add(int u,int v){
	e[++e_id] = {v, h[u]};
	h[u] = e_id;
}

void create_tree(int u, int father){
	fa[u] = father;
	Size[u] = 1;

	for(int i=h[u];i;i=e[i].next){
		int v=e[i].v;
		if(v!=father){
			create_tree(v, u);
			Size[u] += Size[v];
			if(Size[wc[u]]<Size[v])
				__填空(1)__;
		}
	}
}

void dfs(int u, int Top){
	top[u] = __填空(1)__;
	dfn[u] = ++dfn_id;

	// 如果有重儿子，则继续延伸这根链, Top 不边
	if(wc[u]) dfs(__填空(2)__);

	// 深搜轻儿子，轻儿子是一条新的链
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].v;
		if(v!=fa[u] && __填空(3)__){
			dfs(__填空(4)__);
		}
	}
}

int get_lca(int u, int v){
	while(__填空(5)__){
		if(dfn[u]>dfn[v]) __填空(6)__;
		else v = __填空(7)__;
	}
	return dfn[u]<dfn[v] ? __填空(8)__ : __填空(9)__;
}

int main(){
	scanf("%d%d%d",&n, &m, &s);

	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x, &y);
		add(x, y);
		add(y, x);
	}

	create_tree(s, 0); // 建树，算出每个顶点的重儿子
	dfs(__填空(10)__); // 树链剖分，算出每个顶点所属重链的链头

	for(int i=1;i<=m;i++){
		scanf("%d%d",&x, &y);
		printf("%d\n", get_lca(x,y));
	}

	return 0;
}

填空(1)：{{ input(1) }}

填空(2)：{{ input(2) }}

填空(3)：{{ input(3) }}

填空(4)：{{ input(4) }}

填空(5)：{{ input(5) }}

填空(6)：{{ input(6) }}

填空(7)：{{ input(7) }}

填空(8)：{{ input(8) }}

填空(9)：{{ input(9) }}

填空(10)：{{ input(10) }}