题意描述：
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 (n) 个等待点，有 (n−1) 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。
参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 (n) 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。
小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？
最近公共祖先 水题。
一句话题意，让你找到一个点使得给出的三个点到这个点的距离尽可能的小。
手玩样例可以发现，他只会是任意两点之间的最近公共祖先，就直接枚举一下就行。
具体证明的话，就是说这样会使重复的路径尽可能的少。 (bushi).
好像还有一种 (O(1)) 的做法，主要是我没看懂。
但树剖常数小， (5e5) 的数据跑的没有问题。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e5+10;
int n,m,u,v,x,y,z,ans,id,tot;
int dep[N],siz[N],son[N],top[N],head[N],fa[N];
struct node
{
int to,net;
}e[N<<1];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void add(int x,int y)
{
e[++tot].to = y;
e[tot].net = head[x];
head[x] = tot;
}
void get_tree(int x)
{
dep[x] = dep[fa[x]] + 1; siz[x] = 1;
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(to == fa[x]) continue;
fa[to] = x;
get_tree(to);
siz[x] += siz[to];
if(siz[to] > siz[son[x]]) son[x] = to;
}
}
void dfs(int x,int topp)
{
top[x] = topp;
if(son[x]) dfs(son[x],topp);
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(to == fa[x] || to == son[x]) continue;
dfs(to,to);
}
}
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]];
}
return dep[x] <= dep[y] ? x : y;
}
int dis(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-1; i++)
{
u = read(); v = read();
add(u,v); add(v,u);
}
get_tree(1); dfs(1,1);
for(int i = 1; i <= m; i++)
{
x = read(); y = read(); z = read(); ans = 2147483647;
int Lca = lca(x,y);
int a = dis(x,Lca), b = dis(y,Lca), c = dis(z,Lca);
if(ans > a+b+c)
{
ans = a+b+c;
id = Lca;
}
Lca = lca(x,z);
a = dis(x,Lca), b = dis(y,Lca), c = dis(z,Lca);
if(ans > a+b+c)
{
ans = a+b+c;
id = Lca;
}
Lca = lca(y,z);
a = dis(x,Lca), b = dis(y,Lca), c = dis(z,Lca);
if(ans > a+b+c)
{
ans = a+b+c;
id = Lca;
}
printf("%d %d
",id,ans);
}
return 0;
}