解析

蒟蒻用的办法比较蠢，不如上面的各位大佬，直接化成一个式子了，我还是分类讨论做的。

下面正文。

猜想：最优集合点一定是三点任意两对点对应的路径的交点。

不妨这样想，如果任意两个人经过同一条路径，那么就要支付双倍的价钱，为了使支付的钱最少，我们就要使得这种情况出现的最少。由于图是一颗树，如果选择三点交点，一定不会出现这样的边。

那么如何求交点呢？

可以分成两种情况：

1、三个点都在以某个点为根的子树中。

2、有两个点在以某个点为根的子树，另一个点在它上面。

判断比较麻烦，由于无法知道三点确切的相对位置关系，所以这就导致情况2分出来好几种判断法则。实际上它们本质是一样的。

参考代码

吸氧最优解第二页，不吸氧掉到最后一页去了（摊。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<string>

#include<cstdlib>

#include<queue>

#include<vector>

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

#define N 500010

#define MOD 2520

#define E 1e-12

using namespace std;

inline int read()

{

	int f=1,x=0;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

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

	return x*f;

}

struct rec{

	int next,ver;

}g[N<<1];

int head[N],tot,n,m;

inline void add(int x,int y)

{

	g[++tot].ver=y;

	g[tot].next=head[x],head[x]=tot;

}

int size[N],top[N],son[N],fa[N],dep[N],id[N],cnt;

inline void dfs1(int x,int f,int deep)

{

	size[x]=1,fa[x]=f,dep[x]=deep;

	int maxson=-1;

	for(int i=head[x];i;i=g[i].next){

		int y=g[i].ver;

		if(y==f) continue;

		dfs1(y,x,deep+1);

		size[x]+=size[y];

		if(maxson<size[y]) maxson=size[y],son[x]=y;

	}

}

inline void dfs2(int x,int topf)

{

	id[x]=++cnt,top[x]=topf;

	if(!son[x]) return;

	dfs2(son[x],topf);

	for(int i=head[x];i;i=g[i].next){

		int y=g[i].ver;

		if(y==fa[x]||y==son[x]) continue;

		dfs2(y,y);

	}

}

inline int lca(int x,int y)

{

	while(top[x]!=top[y]){

		if(dep[top[x]]<dep[top[y]]) swap(x,y);

		x=fa[top[x]];

	}

	if(dep[x]>dep[y]) swap(x,y);

	return x;

}

inline int dist(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}//两点距离

int main()

{

	n=read(),m=read();

	for(int i=1;i<n;++i){

		int u=read(),v=read();

		add(u,v),add(v,u);

	}

	dfs1(1,0,1);dfs2(1,1);//树剖LCA

	while(m--){

		int x=read(),y=read(),z=read();

		int k1=lca(x,y),k2=lca(y,z),k3=lca(x,z);//f**k lca

		if(k1==k2&&k2==k3)//case 1

			printf("%d %d\n",k1,dep[x]+dep[y]+dep[z]-3*dep[k1]);

		else if(k1!=k2&&k2!=k3&&k1==k3)

			printf("%d %d\n",k2,dist(k2,x)+dist(y,z));

		else if(k1!=k3&&k3!=k2&&k1==k2)

			printf("%d %d\n",k3,dist(k3,y)+dist(x,z));

		else if(k2!=k1&&k1!=k3&&k2==k3)//case 2

			printf("%d %d\n",k1,dist(k1,z)+dist(x,y));

	}

	return 0;

}