题目描述

输入

输出

样例输入

6 4

1 2

2 3

2 4

4 5

5 6

4 5 6

6 3 1

2 4 4

6 6 6

样例输出

5 2

2 5

4 1

6 0

---

题解

倍增LCA

首先有集合点必定在三点中两个点的LCA处，大概画一下就看出来了。

然后有x到y的距离为deep[x]+deep[y]-2*deep[lcaxy]

那么x、y、z三点到lcaxy的距离为deep[x]+deep[y]-2*deep[lcaxy]+deep[lcaxy]+deep[x]-deep[lcaxyz]

到lcaxz、lcayz同理。

可以看出集合点的选择只和deep[lca]有关，于是求一下最大值，再减掉就好了。

#include 
     
      #include 
      
       using namespace std;int head[500010] , to[1000010] , next[1000010] , cnt , log[500010] , fa[500010][21] , deep[500010];void add(int x , int y){	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs(int x){	int i;	for(i = 1 ; i <= log[deep[x]] ; i ++ ) fa[x][i] = fa[fa[x][i - 1]][i - 1];	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x][0])			fa[to[i]][0] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i]);}int getlca(int x , int y){	int i;	if(deep[x] < deep[y]) swap(x , y);	for(i = log[deep[x] - deep[y]] ; ~i ; i -- )		if(deep[x] - (1 << i) >= deep[y])			x = fa[x][i];	if(x == y) return x;	for(i = log[deep[x]] ; ~i ; i -- )		if(fa[x][i] != fa[y][i])			x = fa[x][i] , y = fa[y][i];	return fa[x][0];}int main(){	int n , m , i , x , y , z , xy , xz , yz , t;	scanf("%d%d" , &n , &m);	for(i = 1 ; i < n ; i ++ )		scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);	for(i = 2 ; i <= n ; i ++ ) log[i] = log[i >> 1] + 1;	dfs(1);	while(m -- )	{		scanf("%d%d%d" , &x , &y , &z);		xy = getlca(x , y) , xz = getlca(x , z) , yz = getlca(y , z) , t = deep[x] + deep[y] + deep[z] - 2 * deep[getlca(xy , z)];		if(deep[xy] > deep[xz] && deep[xy] > deep[yz]) printf("%d %d\n" , xy , t - deep[xy]);		else if(deep[xz] > deep[yz]) printf("%d %d\n" , xz , t - deep[xz]);		else printf("%d %d\n" , yz , t - deep[yz]);	}	return 0;}