70pts

求LCA用的欧拉序+ST表

代码：

#include<iostream>
#include<cstdio>
#define N 500010
using namespace std;
inline void read(int &x){
	char c=getchar();x=0;int f=0;
	for(;!isdigit(c);c=getchar()) f|=(c=='-');
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	x=f?-x:x;
}
void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct Edge{
	int v,nxt;
}E[N*2];
int head[N],tote;
void addEdge(int u,int v){
	E[++tote].v=v;
	E[tote].nxt=head[u];
	head[u]=tote;
}
int dfn[N];
int dep[N];
int cnt;
int fir[N];
void dfs(int x,int fa_x){
	dfn[++cnt]=x;
	dep[x]=dep[fa_x]+1;
	fir[x]=cnt;
	for(int i=head[x];i;i=E[i].nxt){
		int v=E[i].v;
		if(v==fa_x) continue;
		dfs(v,x);
		dfn[++cnt]=x;
	}
}
int F[N][30];
int mlog[N];
int query(int l,int r){
	int x=mlog[r-l+1];
	if(dep[F[l][x]]<dep[F[r-(1<<x)+1][x]]){
		return F[l][x];
	}
	return F[r-(1<<x)+1][x];
}
void st_do(int n){
	for(int i=1;i<=n;i++){
		F[i][0]=dfn[i];
	}
	for(int i=2;i<=n;i++){
		mlog[i]=mlog[i>>1]+1;
	}
	for(int j=1;j<=30;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(dep[F[i][j-1]]<dep[F[i+(1<<j-1)][j-1]]){
				F[i][j]=F[i][j-1];
			}
			else F[i][j]=F[i+(1<<j-1)][j-1];
		}
	}
}
int main(){
//	freopen("lca.in","r",stdin);
//	freopen("lca.out","w",stdout);
	int n,m,s;
	read(n);read(m);read(s);
	for(int i=1;i<n;i++){
		int u,v;
		read(u);read(v);
		addEdge(u,v);
		addEdge(v,u);
	}
	dfs(s,s);
	st_do(cnt);
	while(m--){
		int u,v;
		read(u);read(v);
		if(fir[u]<fir[v]){
			write(query(fir[u],fir[v]));puts("");
		}
		else{
			write(query(fir[v],fir[u]));puts("");
		}
	}
	return 0;
}