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

浅谈\(RMQ\)：https://www.cnblogs.com/AKMer/p/10128219.html

题目传送门：https://www.luogu.org/problemnew/show/P3379

\(st\)表也可以求\(lca\)。在带回溯的\(dfs\)上，两个点的\(lca\)就是在该序列上第一次出现的区间内深度最小的那个点。

至于这个序列有多长，因为每个点会出现度数次，度数总和是\(2*(n-1)\)。

时间复杂度：\(O(nlogn+m)\)

空间复杂度：\(O(nlogn)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=5e5+5;

int n,m,rt,tot,cnt;

int f[21][maxn<<1],Log[maxn<<1];

int pos[maxn],dep[maxn],dfn[maxn<<1];

int now[maxn],pre[maxn<<1],son[maxn<<1];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='0')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void add(int a,int b) {

	pre[++tot]=now[a];

	now[a]=tot,son[tot]=b;

}

void dfs(int fa,int u) {

	dep[u]=dep[fa]+1;

	pos[u]=++cnt,dfn[cnt]=u,f[0][cnt]=u;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(v!=fa)dfs(u,v),dfn[++cnt]=u,f[0][cnt]=u;

}

int calc(int a,int b) {

	return dep[a]<dep[b]?a:b;

}

void make_st() {

	Log[0]=-1;

	for(int i=1;i<=cnt;i++)

		Log[i]=Log[i>>1]+1;

	for(int i=1;i<=20;i++)

		for(int j=1;j+(1<<i)-1<=cnt;j++)

			f[i][j]=calc(f[i-1][j],f[i-1][j+(1<<(i-1))]);

}

int query(int l,int r) {

	int x=Log[r-l+1];

	return calc(f[x][l],f[x][r-(1<<x)+1]);

}

int main() {

	n=read(),m=read(),rt=read();

	for(int i=1;i<n;i++) {

		int a=read(),b=read();

		add(a,b),add(b,a);

	}dfs(0,rt);make_st();

	for(int i=1;i<=m;i++) {

		int a=pos[read()],b=pos[read()];

		if(b<a)swap(a,b);

		printf("%d\n",query(a,b));

	}

	return 0;

}

巴特西

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

最新文章

热门文章