Problem
题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1N−1 行每行包含两个正整数 x, yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 MM 行每行包含两个正整数 a, ba,b，表示询问 aa 结点和 bb 结点的最近公共祖先。
输出格式
输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。
输入输出样例
输入 #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
说明/提示
对于 30\%30% 的数据，N\leq 10N≤10，M\leq 10M≤10。
对于 70\%70% 的数据，N\leq 10000N≤10000，M\leq 10000M≤10000。
对于 100\%100% 的数据，N\leq 500000N≤500000，M\leq 500000M≤500000。
样例说明：
该树结构如下：
第一次询问：2, 42,4 的最近公共祖先，故为 44。
第二次询问：3, 23,2 的最近公共祖先，故为 44。
第三次询问：3, 53,5 的最近公共祖先，故为 11。
第四次询问：1, 21,2 的最近公共祖先，故为 44。
第五次询问：4, 54,5 的最近公共祖先，故为 44。
故输出依次为 4, 4, 1, 4, 44,4,1,4,4。
2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。
Codes
- 留个备忘
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 5e5+10;
int n, q, rt;
struct tree{
vector<int>G[maxn];
int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn];
void add(int x, int y){
G[x].push_back(y);
G[y].push_back(x);
}
void dfs(int x, int f){
siz[x] = 1;
for(int y : G[x]){
if(y==f)continue;
fa[y] = x;
dep[y] = dep[x]+1;
dfs(y,x);
if(siz[y] > siz[son[x]])son[x] = y;//x的重儿子
siz[x] += siz[y];
}
}
void dfs(int x, int y, int f){
//轻重链剖分
top[x] = y; //所在链链顶
if(son[x])dfs(son[x], y,x); //重链往下去不用更新链顶
for(int y : G[x]){
if(y==f)continue;
if(y==son[x])continue;
dfs(y,y,x); //更新y为链顶
}
}
//LCA复杂度：暴力O(n), 倍增O(logn~nlogn), TarjianO(logn~n), 树剖O(logn)
int lca(int x, int y){
while(top[x] != top[y]){
//不在同一条链上 每次链顶深度较大的点往上爬
if(dep[top[x]] < dep[top[y]])swap(x,y);
x = fa[top[x]]; //进入新的链
}
if(dep[x] < dep[y])return x;//进入同一条链上时, 深度小的点在前面
return y;
}
void do_lca(int rt){
dfs(rt,-1);
dfs(rt,-1,-1);
}
}treea;
int main(){
IOS;
cin>>n>>q>>rt;
for(int i = 2; i <= n; i++){
int u, v; cin>>u>>v;
treea.add(u,v);
}
treea.do_lca(rt);
for(int i = 1; i <= q; i++){
int u, v; cin>>u>>v;
cout<<treea.lca(u,v)<<"\n";
}
return 0;
}
