题目描述
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有N个等待点，有N-1条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在N个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入格式
第一行两个正整数N和M（N<=500000，M<=500000），之间用一个空格隔开。分别表示等待点的个数（等待点也从1到N进行编号）和获奖所需要完成集合的次数。 随后有N-1行，每行用两个正整数A和B，之间用一个空格隔开，表示编号为A和编号为B的等待点之间有一条路。 接着还有M行，每行用三个正整数表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式
一共有M行，每行两个数P,C，用一个空格隔开。其中第i行表示第i次集合点选择在编号为P的等待点，集合总共的花费是C个游戏币。

输入输出样例
输入 #1 复制
6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6
输出 #1 复制
5 2
2 5
4 1
6 0

说明/提示
提示：

40%的数据中N<=2000，M<=2000
100%的数据中，N<=500000，M<=500000

简单题意：求一个点，到这三个点的距离最短。

树上距离问题，我们不难想到LCA，然后通过画图，我们不难发现三点间两两之间的lca一定有一个相同的，也可以发现我们选取的lca就是深度最深的那一个（如果没发现取最小值也是可以的）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e5+10;
int n,m,f[N][30],h[N],d[N],lg[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa){
			d[to[i]]=d[x]+1;	dfs(to[i],x);
		}
	}
}
inline int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int dis(int a,int b){
	return d[a]+d[b]-2*d[lca(a,b)];
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a);
	}
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
	while(m--){
		int a,b,c,res;	scanf("%d %d %d",&a,&b,&c);
		int t1=lca(a,b),t2=lca(b,c),t3=lca(a,c);
		if(t1==t2)	res=t3;
		if(t1==t3)	res=t2;
		if(t2==t3)	res=t1;
		printf("%d %d\n",res,dis(res,a)+dis(res,b)+dis(res,c));
	}
	return 0;
}