欧拉序+ST表 O(nlogn+q)求LCA

欧拉序：每次遍历到树上的一个点，就加进欧拉序

如

1

2 3

​ 4 5

这颗树的欧拉序是121343431

这样我们可以发现一个重要的性质：两个点的LCA是欧拉序之间dep最小的点

易发现这是对的，因为LCA肯定会在欧拉序之间，而LCA的祖先不会，因为如果会，说明LCA的这颗子树已经被遍历完了，那之后不会再有另一个节点

因此我们dfs建立欧拉序，在欧拉序上建ST表，每次查u,v的LCA，等价于查找$$[pos[u],pos[v]]$$在ST表上的最小值

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 5e5+10,M=2*N;
int n, m, k, T;
int h[N],e[M],ne[M],idx;
PII val[22][2*N];
int dep[N],_,pos[N];
int Log2[2*N];
void add(int a, int b) {
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
unsigned int A, B, C;
inline unsigned int rng61() {
	A ^= A << 16;
	A ^= A >> 5;
	A ^= A << 1;
	unsigned int t = A;
	A = B;
	B = C;
	C ^= t ^ A;
	return C;
}
void dfs(int u, int p) {
	//cout<<u<<'!'<<endl;
	dep[u]=dep[p]+1;
	val[0][++_] = {dep[u],u};
	pos[u]=_;
	for (int i = h[u]; ~i; i = ne[i]) {
		int k=e[i];
		if(k==p)continue;
		dfs(k,u);
		val[0][++_]={dep[u],u};
	}
}
void initST() {
	for(int i=2;i<=_;i++)Log2[i]=Log2[i/2]+1;
	for(int i=1;i<=20;i++)
		for (int j = 1; j+(1<<i)-1 <= _; j++) {
			val[i][j]=min(val[i-1][j],val[i-1][j+(1<<i-1)]);
		}
}
int query(int l, int r) {
	if(l>r)swap(l,r);
	int len=Log2[r-l+1];
	return min(val[len][l],val[len][r-(1<<len)+1]).second;
}
int main(){
	memset(h,-1,sizeof h);
	scanf("%d%d%u%u%u", &n, &m, &A, &B, &C);
	// 输入树边
	for (int i = 1; i < n; i++) {
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b),add(b,a);
	}
	dfs(1,0);
	initST();
	LL res=0;
	for (int i = 1; i <= m; i++) {
		unsigned int u = rng61() % n + 1, v = rng61() % n + 1;
		//printf("%d %d %d\n",u,v,query(pos[u],pos[v]));
		res^=1LL*i*query(pos[u],pos[v]);
	}
	printf("%lld",res);
}

Tip:

建ST表有个小技巧，可以建一个pair的ST，first存值，second存对应的dep最小的点，这样每次取min的时候可以自动保存最小值所在的点，而不需要另开一个数组