#include<bits/stdc++.h>
const int maxn = 500010;
using namespace std;
vector<int> g[maxn];
int par[20][maxn], dep[maxn], n, m, ml;
//求每个点的深度,并初始化节点v的距离为2^0的父亲
void dfs(int v, int p, int d)
{
par[0][v] = p; dep[v] = d;
for (int i = 0; i < g[v].size(); ++i){
if (g[v][i] != p) dfs(g[v][i], v, d + 1);
}
return ;
}
void init(int s)
{
dfs(s, 0, 0);
int sum = 1;//最多跳多少次
while (sum <= n) sum <<= 1, ++ml;
for (int k = 0; k < ml; ++k){//枚举往上跳2^k步
for (int v = 1; v <= n; ++v){
if (v == s) continue;
//往上2^k步的父亲再往上2^k步就是2^(k+1)步了
par[k + 1][v] = par[k][par[k][v]];
}
}
return ;
}
int lca(int u, int v)
{
if (dep[u] > dep[v]) swap(u, v);
//把深的移上来
for (int k = 0; k < ml; ++k){
if (((dep[v] - dep[u]) >> k) & 1) v = par[k][v];
}
if (u == v) return u;
//这里就相当于当到LCA的距离的二进制位为1就往上跳
for (int k = ml - 1; k >= 0; --k){
if (par[k][u] != par[k][v]) u = par[k][u], v = par[k][v];
}
//注意走完其实还差一个2^0步
//因为u和v不等就至少是父亲才能相等,本身判断不到
return par[0][u];
}
int main()
{
int u, v, s;
scanf("%d %d %d", &n, &m, &s);
int t = n;
while (--t){
scanf("%d %d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
init(s);
while (m--){
scanf("%d %d", &u, &v);
printf("%d\n", lca(u, v));
}
return 0;
}
https://www.luogu.org/problemnew/show/P3398
一道不是全裸的题,还让我写了个对拍程序。
就是保存一下LCA的深度,然后两个人的两个点两两配对向上走,只要有一对能碰到且深度大于等于自己LCA的深度,就说明能碰到。
int faldep, fardep;
bool collide(int l, int r)
{
if (dep[l] > dep[r]){
for (int k = 0; k < ml; ++k){
if (((dep[l] - dep[r]) >> k) & 1) l = par[k][l];
}
}else{
for (int k = 0; k < ml; ++k){
if (((dep[r] - dep[l]) >> k) & 1) r = par[k][r];
}
}
if (l == r && dep[l] >= faldep && dep[r] >= fardep) return true;
for (int k = ml - 1; k >= 0; --k){
if (par[k][l] != par[k][r]) l = par[k][l], r = par[k][r];
}
l = par[0][l], r = par[0][r];
if (l == r && dep[l] >= faldep && dep[r] >= fardep) return true;
return false;
}