题目

link

题解

弱化题目条件

如果是两个人的话，集合点肯定在这两个点的lca上

而这里是三个人，怎么办？

猜测发现一定在其中两个人的lca上

分别求出两两的lca，3种情况分别比较大小即可

代码

#include<bits/stdc++.h>
const int N = 5e5 + 10;
using namespace std;
int n, m;
int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

int head[N], nxt[N << 1], to[N << 1], cnt = 1;
int fa[N][20];
int depth[N];
void add(int x, int y)
{
	to[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void dfs(int u, int fath)
{
	fa[u][0] = fath;
	depth[u] = depth[fath] + 1;
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if(v == fath) continue;
		dfs(v, u);
	}
}

void initlca()
{
	for(int j = 1;j < 20;j++)
	{
		for(int i = 1;i <= n;i++)
		{
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
		}
	}
}

int querylca(int x, int y)
{
	if(depth[x] < depth[y]) swap(x, y);

	for(int j = 19;j >= 0;j--)
	{
		if(depth[fa[x][j]] >= depth[y])
		{
			x = fa[x][j];
		}
	}

	if(x == y) return x;

	for(int j = 19;j >= 0;j--)
	{
		if(fa[x][j] != fa[y][j])
		{
			x = fa[x][j], y = fa[y][j];
		}
	}

	return fa[x][0];
}

int main()
{
	n = read(), m = read();
	int a, b; 
	for(int i = 1;i <= n - 1;i++)
	{
		a = read(), b = read();
		add(a, b), add(b, a);
	}
	dfs(1, 0);
	initlca();
	int x, y, z;
	while(m --)
	{
		x = read(), y = read(), z = read();
		int xy = querylca(x, y);
		int yz = querylca(y, z);
		int xz = querylca(x, z);
		int xyz = querylca(xy, z);
		int yzx = querylca(yz, x);
		int xzy = querylca(xz, y);
		int xy_long = (-2) * depth[xy] + depth[x] + depth[y] - 2 * depth[xyz] + depth[z] + depth[xy];
		int yz_long = (-2) * depth[yz] + depth[y] + depth[z] - 2 * depth[yzx] + depth[x] + depth[yz];
		int xz_long = (-2) * depth[xz] + depth[x] + depth[z] - 2 * depth[xzy] + depth[y] + depth[xz];

		if(xy_long <= yz_long && xy_long <= xz_long)
		{
			printf("%d %d\n", xy, xy_long);
		}
		else if(yz_long <= xy_long && yz_long <= xz_long)
		{
			printf("%d %d\n", yz, yz_long);
		}
		else if(xz_long <= xy_long && xz_long <= yz_long)
		{
			printf("%d %d\n", xz, xz_long);
		}

	}
	return 0;
}