#C240924E. DFS 序求 LCA

标签（Label）

• LCA

• 模板

网址（Website）

冷门科技 —— DFS 序求 LCA

【模板】最近公共祖先（LCA）

练习题：#C240924A. 避难

题解（Solution）

$\qquad$说一下关于时间复杂度的问题，这是一个 $O(nlogn)$ 预处理，$O(1)$ 查询的算法。有关 $\verb!__lg!$ 函数，它是直接通过位运算来判断的，而不是通过一次一次除 $2$ ，因此可以直接看作 $O(1)$ 的函数。

$\qquad$注意第 $30$ 行的 d=__lg(y-x++) ，这个地方很容易写成 d=__lg(y-x+1) ，这样是不对的。d=__lg(y-x++) 这行代码可以看作 d=__lg(y-x),x++; 两个语句。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 501234;
bool ST;

vector<int> ft[N];
int n,m,s;

int dfn[N],idx;
int f[N][20];
void dfs(int x,int fa){
	f[dfn[x]=++idx][0] = fa;
	for(auto y:ft[x]) if(y!=fa) dfs(y,x);
}

inline int cmn(int x,int y){return dfn[x]<dfn[y] ? x : y;}

inline int lca(int x,int y){
	if(x==y) return x;
	if((x=dfn[x])>(y=dfn[y])) swap(x,y);
	int d = __lg(y-x++);
	return cmn(f[x][d], f[y-(1<<d)+1][d]);
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	cin>>n>>m>>s;int Tim = clock();
	For(i,2,n){
		int x,y;cin>>x>>y;
		ft[x].emplace_back(y);
		ft[y].emplace_back(x);
	}dfs(s,0);
	For(j,1,__lg(n))
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j] = cmn(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	For(i,1,m) cout<<lca(rd(),rd())<<'\n'; 
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}