题目描述
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有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个游戏币。
输入输出样例
说明
提示：
40%的数据中N<=2000，M<=2000
100%的数据中，N<=500000，M<=500000
分析：
首先考虑只有两个点的情况，很明显树上两点A,B之间距离为$ dep[a]+dep[b]-dep[LCA(a,b)] $ （dep表示该点到根节点的距离（即深度））
那么这给我们的启示是：对于三个点能不能用也用LCA求解
接下来我们就不难发现，对于树上三点a,b,c，它们两两之间都有一个LCA，一共就有三个，这三个中有两个是同一个且深度较小
证明：我们假设$ x=LCA(a,b),y=LCA(a,c),且x>y $
则对于$ z=LCA(b,c) $,首先存在路径$b->x,a->x->y$,则有路径$b->x->y$，又因为$c->y$，所以$ LCA(b,c)=y=LCA(a,c) $
接下来我们先找集合点，假设集合点存在于那个较深的LCA（即上面的x）
那么我们不难发现，不管是将x上移还是下移，都会使一个点的路径减少$w$，但另两个点的路径都会增加$w$
因此将点放在那个较深的LCA最优
关于计算路径，我们用上面所设的点表示出来是
$$ ans=dep[a]+dep[b]-2*dep[x]+dep[x]+dep[c]-2*dep[y]$$
$$=dep[a]+dep[b]+dep[c]-dep[x]+2*dep[y]$$
$$=dep[a]+dep[b]+dep[c]-dep[x]-dep[y]-dep[z](y==z)$$
我们发现不管a,b,c如何变化，由于x,y,z的值不会变化，所以ans的值也不会变化，直接代入求值即可
#include<iostream>
#include<string>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
struct node{
int to,nxt;
}sq[];
int fa[][],n,m,dep[],head[],all=,low[]; void add(int u,int v)
{
all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
all++;sq[all].to=u;sq[all].nxt=head[v];head[v]=all;
} void dfs(int u,int fu)
{
dep[u]=dep[fu]+;
fa[u][]=fu;
int i;
for (i=;i<=low[dep[u]];i++) fa[u][i]=fa[fa[u][i-]][i-];
for (i=head[u];i;i=sq[i].nxt)
{
int v=sq[i].to;
if (v!=fu) dfs(v,u);
}
} int LCA(int u,int v)
{
if (dep[u]<dep[v]) swap(u,v);
while (dep[u]>dep[v]) u=fa[u][low[dep[u]-dep[v]]];
if (u==v) return u;
int i;
for (i=low[dep[u]];i>=;i--)
if (fa[u][i]!=fa[v][i]) {u=fa[u][i];v=fa[v][i];}
return fa[u][];
} int main()
{
scanf("%d%d",&n,&m);
int i;
memset(head,,sizeof(head));
for (i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
low[]=;
for (i=;i<=n;i++) low[i]=low[i>>]+;
dep[]=;
dfs(,);
for (i=;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int x=LCA(a,b),y=LCA(a,c),z=LCA(b,c);
int ansp,ansd;
if (x==y) ansp=z;
else if (x==z) ansp=y;
else if (y==z) ansp=x;
ansd=dep[a]+dep[b]+dep[c]-dep[x]-dep[y]-dep[z];
printf("%d %d\n",ansp,ansd);
}
return ;
}