提交记录

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,root,money;
int h[500010],fa[500010][25];
vector<int> a[500010];
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}
void dfs(int x,int father)
{
	h[x]=h[father]+1;
	fa[x][0]=father;
	for (int i=0;i<a[x].size();i++)
	{
		if (a[x][i]==father) continue;
		dfs(a[x][i],x);
	}
}
void pre()
{
	for (int i=1;(1<<i)<=n;i++)
		for (int j=1;j<=n;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1];
}
int lca(int x,int y)
{
	if (y>x) swap(x,y);
	int cha=h[x]-h[y];
	if (cha)
	{
		for (int i=log2(cha);i>=0;i--)
			if ((1<<i)<=cha)
			{
				cha-=(1<<i);
				x=fa[x][i];
			}
	}
	if (x==y) return x;
	for (int i=log2(h[x]);i>=0;i--)
		if (fa[x][i]!=fa[y][i])
		{
			y=fa[y][i];
			x=fa[x][i];
		}
	return fa[x][0];
}
void ans(int x,int y,int z)
{
	int rxy=lca(x,y);
	int ryz=lca(y,z);
	int rxz=lca(x,z);
	if (rxy==ryz && ryz==rxz) {root=rxy;money=h[x]+h[y]+h[z]-h[root]*3;}
	if (rxy==ryz && ryz!=rxz) {root=rxz;money=h[x]+h[z]-h[root]*2+h[y]-h[rxy]+h[root]-h[rxy];}
	if (ryz==rxz && rxy!=ryz) {root=rxy;money=h[x]+h[y]-h[root]*2+h[z]-h[ryz]+h[root]-h[ryz];}
	if (rxy==rxz && rxz!=ryz) {root=ryz;money=h[y]+h[z]-h[root]*2+h[x]-h[rxy]+h[root]-h[rxy];}
}
	
int main()
{
	n=read(),m=read();
	for (int i=1;i<n;i++)
	{
		int aa,b;
		aa=read(),b=read();
		a[aa].push_back(b);
		a[b].push_back(aa);
	}
	dfs(1,0);
	pre();
	for (int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		ans(x,y,z);
		printf("%d %d\n",root,money);
	}
	return 0;
}

QwQ