rt,用lct的做法教了两次，一次splay维护的是深度递增，一次是深度递减，两个做法的空间一个是48MB,一个是38MB。按道理两者不应该是对称的吗，评测波动应该没有那么明显吧。

48MB的：

#include<bits/stdc++.h>
#define maxn 500005
#define lc ch[x][0]
#define rc ch[x][1]
int n,m,s,fa[maxn],ch[maxn][2];
std::vector<int>vec[maxn];
void dfs(int u)
{
	for(int i = vec[u].size()-1,v;v = vec[u][i],i>=0;--i)
		if(v!=fa[u])fa[v] = u,dfs(v);
}
inline bool isroot(int x){return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];}
inline bool get(int x){return x == ch[fa[x]][1];}
inline void rorate(int x)
{
	int y = fa[x],z = fa[y],k = get(x);
	if(!isroot(y))ch[z][get(y)] = x;
	ch[y][k] = ch[x][!k],fa[ch[x][!k]] = y;
	ch[x][!k] = y,fa[x] = z,fa[y] = x;
}
void splay(int x)
{
	for(int f;f = fa[x],!isroot(x);rorate(x))
		if(!isroot(f))rorate(get(f) == get(x)?f:x);
}
int access(int x)
{
	int p = 0;
	while(x)splay(x),lc = p,p = x,x = fa[x];
	return p;
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1,u,v;i<n;++i)
	{
		scanf("%d%d",&u,&v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(s);
	for(int i = 1,x,y;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",(access(x),access(y)));
	}
	return 0;
}

38MB的：

#include<bits/stdc++.h>
#define maxn 500005
#define lc ch[x][0]
#define rc ch[x][1]
int n,m,s,fa[maxn],ch[maxn][2];
std::vector<int>vec[maxn];
void dfs(int u)
{
	for(int i = vec[u].size()-1,v;v = vec[u][i],i>=0;--i)
		if(v!=fa[u])fa[v] = u,dfs(v);
}
inline bool isroot(int x){return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];}
inline bool get(int x){return x == ch[fa[x]][1];}
inline void rorate(int x)
{
	int y = fa[x],z = fa[y],k = get(x);
	if(!isroot(y))ch[z][get(y)] = x;
	ch[y][k] = ch[x][!k],fa[ch[x][!k]] = y;
	ch[x][!k] = y,fa[x] = z,fa[y] = x;
}
void splay(int x)
{
	for(int f;f = fa[x],!isroot(x);rorate(x))
		if(!isroot(f))rorate(get(f) == get(x)?f:x);
}
int access(int x)
{
	int p = 0;
	while(x)splay(x),rc = p,p = x,x = fa[x];
	return p;
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i = 1,u,v;i<n;++i)
	{
		scanf("%d%d",&u,&v);
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	dfs(s);
	for(int i = 1,x,y;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",(access(x),access(y)));
	}
	return 0;
}