20200921day17 刷题记录

1 POJ1330 LCA模板

2 洛谷LCA模板

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define INF 9999999
using namespace std;
struct node{
	int to,next;
}edge[500005<<1];
int head[500005];
int tot,cnt;
int n,m,s;
void add(int x,int y){
	edge[++cnt].next=head[x];
	edge[cnt].to=y;
	head[x]=cnt;
}
int depth[500005],fa[500001][22],lg[50001];
//depth表示每个节点的深度,fa[i][j]表示节点i的2^j级祖先
//lg表示log_2(i)+1的值
void fd(){
	for(int i=1;i<=n;i++){//?
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
}
void dfs(int now,int fath){
	fa[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;i<=lg[depth[now]];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
		//now的2^i祖先等于now的2^i-1祖先的2^i-1祖先
		//2^i=2^i-1+2^i-1
	}
	for(int i=head[now];i;i=edge[i].next){
		if(edge[i].to!=fath) dfs(edge[i].to,now);
	}
}
int lca(int x,int y){
	if(depth[x]<depth[y]) swap(x,y);//不妨设x深度>=y
	while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];
	//调到同一深度
	if(x==y) return x;//二者重合 LCA就是x
	for(int k=lg[depth[x]]-1;k>=0;k--){
		//不断向上跳
		if(fa[x][k]!=fa[y][k])
			x=fa[x][k],y=fa[y][k];
			//要跳到它们LCA的下面一层，所以肯定不相等，如果不相等就跳过去
	}
	return fa[x][0];//返回父亲节点
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	fd();
	dfs(s,0);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d
",lca(x,y));
	}
	return 0;
}