欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

几种求LCA的姿势

程序员文章站 2022-07-07 19:32:25
...

 FZSZ Online Judge #815. LCA

题目描述

给定一个 n 个点的有根树,q 次询问 (x,y) 的最近公共祖先

输入格式

一行输入一个正整数 n

以下 n1 行, 每行输入两个正整数 (x,y), 表示 xy有一条边

一行输入一个正整数 q

以下 q 行, 每行输入两个正整数 (x,y), 表示询问 lca(x,y)

输出格式

设第 i 次询问的答案为 xixi, 输出 qi=1nq-ixi(mod264)

//不知道有没搞错反正是 ans = ans * n + Lca(x, y);

样例输入

3
1 2
1 3
3
1 2
1 3
2 3

样例输出

13

数据范围

n,q106,x,yn,

倍增算法(在线处理)

#include<cstdio>
#include<iostream>
#include<cmath>
#define ull unsigned long long
#define BIG 2333333
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
ull mod;
inline int read(){
	char c;
	while(c=getchar(),c>'9'||c<'0');
	int data=c-48;
	while(c=getchar(),c>='0'&&c<='9')
		data=(data<<1)+(data<<3)+c-48;
	return data;
}
int nxt[BIG],las[BIG],to[BIG],rd[BIG],dep[BIG],fa[BIG][24];
int n,q,tot,x,y;
ull ans;
inline void add(int x,int y){
	nxt[++tot]=las[x];
	las[x]=tot;
	to[tot]=y;
	++rd[y];
}
inline void dfs(int now){
	for(register int e=las[now];e;e=nxt[e]){
		dep[to[e]]=dep[now]+1;
		fa[to[e]][0]=now;
		dfs(to[e]);
	}
}
inline void ST(){
	FOR(i,1,20)
		FOR(j,1,n)
			fa[j][i]=fa[fa[j][i-1]][i-1];
}
inline void swap(int &x,int &y){
	int t=x;
	x=y;
	y=t;
}
inline int LCA(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	for(register int i=20;i>=0;--i)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y)
		return x;
	for(register int i=20;i>=0;--i)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int wr[101];
inline void write(unsigned long long a){
	if(!a){
		putchar(48);
		return;
	}
	while(a)
		wr[++wr[0]]=a%10,a/=10;
	while(wr[0])
		putchar(48+wr[wr[0]--]);
	return;
}
int main(){
	n=read();
	FOR(i,1,n-1){
		x=read();
		y=read();
		add(x,y);
	}
	FOR(i,1,n)
		if(!rd[i]){
			dep[i]=1;
			dfs(i);
			break;
		}
	q=read();
	ST();
	mod=1;
	FOR(i,1,63)
		mod=(ull)(mod<<1);
	while(q--){
		x=read();
		y=read();
		ans=ans*n+LCA(x,y);
		if(ans<0){
			ans+=mod;
			ans+=mod;
		}
	}
	write(ans);
	return 0;
}

树链剖分(在线处理)

#include<cstdio>
#include<iostream>
#define BIG 2333333
#define ll unsigned long long 
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
namespace TCP{
	int nxt[BIG],las[BIG],to[BIG],deg[BIG];
	int dep[BIG],sz[BIG],top[BIG],f[BIG];
	int n,m,x,y,tot;
	inline void add(int x,int y){
		nxt[++tot]=las[x];
		las[x]=tot;
		to[tot]=y;
		++deg[y];
		return;
	}
	inline void dfs1(int now){
		sz[now]=1;
		for(register int e=las[now];e;e=nxt[e]){
			dep[to[e]]=dep[f[to[e]]=now]+1;
			dfs1(to[e]);
			sz[now]+=sz[to[e]];
		}
		return;
	}
	inline void dfs2(int now,int chain){
		top[now]=chain;
		register int i=0;
		for(register int e=las[now];e;e=nxt[e])
			if(sz[i]<sz[to[e]])
				i=to[e];
		if(!i)
			return;
		dfs2(i,chain);
		for(register int e=las[now];e;e=nxt[e])
			if(to[e]!=i)
				dfs2(to[e],to[e]);
		return;
	}
	inline ll lca(int u,int v){
		for(;top[u]!=top[v];dep[top[u]]>dep[top[v]]?u=f[top[u]]:v=f[top[v]]);
		return (ll)(dep[u]<dep[v]?u:v);
	}
};
using namespace TCP; 
namespace DATA{
	inline void read(int &x){
		char c;
		while(c=getchar(),c>'9'||c<'0');
		x=c-48;
		while(c=getchar(),c>='0'&&c<='9')
			x=(x<<1)+(x<<3)+c-48;
		return;
	}
	int wr[51]; 
	inline void write(ll x){
		while(x)
			wr[++wr[0]]=x%10,x/=10;
		while(wr[0])
			putchar(48+wr[wr[0]--]);
		putchar('\n');
		return;
	}
};
using namespace DATA;
namespace WORK{
	ll ans,mod=1ll;
	inline void work(){
		read(n);
		FOR(i,1,n-1){
			read(x);
			read(y);
			add(x,y);
		}
		FOR(i,1,n)
			if(!deg[i]){
				dfs1(i);
				dfs2(i,i);
				break;
			}
		FOR(i,1,63)
			mod<<=1;
		read(m);
		while(m--){
			read(x);
			read(y);
			ans=ans*n+lca(x,y);
			if(ans<0){
				ans+=mod;
				ans+=mod;
			}
		}
		write(ans); 
	} 
}; 
using namespace WORK;
int main(){
	work();
	return 0;
} 

Tarjan(离线处理)

 

#include<cstdio>
#include<iostream>
#include<vector>
#define BIG 2333333
#define ll unsigned long long 
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
namespace TARJAN{
	int n,m,tot;
	int x,y,z;
	int las[BIG],to[BIG],nxt[BIG],f[BIG],used[BIG],deg[BIG];
	class question{
		public:
		int u[3];
		int lca;
		private:
	}q[BIG];
	vector<int>point[BIG>>1];
	inline void add(int x,int y){
		nxt[++tot]=las[x];
		las[x]=tot;
		to[tot]=y;
		++deg[y];
		return;
	}
	inline int find(int x){
		return f[x]==x?x:f[x]=find(f[x]);
	}
	inline void dfs(int now,int fa){
		used[now]=1;
		register int i,p,other;
		for(i=0;i<(int)point[now].size();++i){
			p=point[now][i];
			for(register int j=0;j<=1;++j){	
				other=q[p].u[j];
				if(other!=now)
					if(used[other])
						q[p].lca=find(other);
			}
		}
		for(register int e=las[now];e;e=nxt[e])
			dfs(to[e],now);
		f[now]=fa;
		return;
	}
}
using namespace TARJAN; 
namespace DATA{
	inline void read(int &x){
		char c;
		while(c=getchar(),c>'9'||c<'0');
		x=c-48;
		while(c=getchar(),c>='0'&&c<='9')
			x=(x<<1)+(x<<3)+c-48;
		return;
	}
	int wr[51]; 
	inline void write(ll x){
		while(x)
			wr[++wr[0]]=x%10,x/=10;
		while(wr[0])
			putchar(48+wr[wr[0]--]);
		putchar('\n');
		return;
	}
};
using namespace DATA;
namespace WORK{
	ll ans,mod=1ll;
	inline void work(){
		read(n);
		FOR(i,1,n-1){
			read(x);
			read(y);
			add(x,y);
		}
		FOR(i,1,n)
			f[i]=i;
		FOR(i,1,63)
			mod<<=1;
		read(m);
		FOR(i,1,m){
			read(q[i].u[0]);
			read(q[i].u[1]);
			point[q[i].u[0]].push_back(i);
			point[q[i].u[1]].push_back(i); 
		}
		FOR(i,1,n)
			if(!deg[i]){
				dfs(i,0);
				break;
			}
		FOR(i,1,m){
			ans=(ll)(ans*n+q[i].lca);
			if(ans<0){
				ans+=mod;
				ans+=mod;
			}
		}
		write(ans);
		return;
	} 
};
using namespace WORK;
int main(){
	work();
	return 0;
}