#include<iostream>
#include<vector>
#define N 500005
int dep[N],anc[N][25];
std::vector<int>G[N];
void dfs(int u,int fa){
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(v==fa)continue;
		dep[v]=dep[u]+1;
		anc[v][0]=u;
		dfs(v,u);
	}
}
int LCA(int u,int v){
	if(dep[u]<dep[v])std::swap(u,v);
	for(int i=23;i>=0;i--)
		if(dep[anc[u][i]]>=dep[v])
			u=anc[u][i];
	if(u==v)return u;
	for(int i=23;i>=0;i--)
		if(anc[u][i]!=anc[v][i])
			u=anc[u][i],v=anc[v][i];
	return anc[u][0];
} 
int n,q;
int main(){
	std::ios::sync_with_stdio(0);
	std::cin>>n>>q;
	for(int i=1;i<n;i++){
		int u,v;
		std::cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dep[1]=1;
	dfs(1,0);
	for(int j=1;j<=23;j++)
		for(int i=1;i<=n;i++)
			anc[i][j]=anc[anc[i][j-1]][j-1];
	while(q--){
		int u,v,w;
		std::cin>>u>>v>>w;
		int L[4]={LCA(u,v),LCA(u,w),LCA(v,w),0};
		if(L[0]==L[1])L[3]=L[2];
		else if(L[0]==L[2])L[3]=L[1];
		else if(L[1]==L[2])L[3]=L[0];
		std::cout<<L[3]<<" "<<dep[u]+dep[v]+dep[w]-dep[L[0]]-dep[L[1]]-dep[L[2]]<<"\n";
	}
} 

很极限，这份代码能不能过完全取决于当前评测机的效率，#8 #9 十分极限，都在 990 ms $\sim$ 1s+ 徘徊。

• https://www.luogu.com.cn/record/169444803 80pts
• https://www.luogu.com.cn/record/169444749 100pts

这两份提交记录都是同一份代码。