题目描述
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有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
题解
对于每次询问，设三个点分别为x1,x2,x3。
两两求lca，得到三个lca，其中最深的那个点为最优集合点。
不会严谨证明，画画图感性理解还是不难的。
然后有了集合点，问题转化为求树上两点间的距离。
随便搞搞就出来了。
/*
qwerta
P4281 [AHOI2008]紧急集合 / 聚会
Accepted
100
代码 C++，2.24KB
提交时间 2018-10-09 18:50:02
耗时/内存
1148ms, 24100KB
*/
#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
char ch=getchar();
int x=;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch)){x=x*+ch-'';ch=getchar();}
return x;
}
const int MAXN=;
struct emm{
int e,f;
}a[*MAXN];
int h[MAXN];
int fa[MAXN],top[MAXN],d[MAXN],siz[MAXN],z[MAXN];
void dfs(int x)
{
siz[x]=,top[x]=x;
int mac=,macc=;
for(int i=h[x];i;i=a[i].f)
if(!d[a[i].e])
{
d[a[i].e]=d[x]+;
fa[a[i].e]=x;
dfs(a[i].e);
siz[x]+=siz[a[i].e];
if(siz[a[i].e]>macc){mac=a[i].e,macc=siz[a[i].e];}
}
z[x]=mac,top[mac]=x;
return;
}
int q[MAXN],dfn[MAXN];
int tot=;
void dfss(int x)
{
q[++tot]=x;
dfn[x]=tot;
if(z[x])dfss(z[x]);
for(int i=h[x];i;i=a[i].f)
if(fa[a[i].e]==x&&a[i].e!=z[x])
dfss(a[i].e);
return;
}
int fitop(int x)
{
if(top[x]==x)return x;
return top[x]=fitop(top[x]);
}
int lca(int u,int v)//树剖求lca
{
while(top[u]!=top[v])
{
if(d[top[u]]<d[top[v]])swap(u,v);
u=fa[top[u]];
}
if(d[u]<d[v])swap(u,v);
return v;
}
int dmin(int x1,int x2,int x3)//找深度最深的点
{
if(d[x1]>=d[x2]&&d[x1]>=d[x3])return x1;
if(d[x2]>=d[x1]&&d[x2]>=d[x3])return x2;
return x3;
}
int dis(int u,int v)//求距离
{
int ans=;
while(top[u]!=top[v])
{
if(d[top[u]]<d[top[v]])swap(u,v);
ans+=dfn[u]-dfn[top[u]]+;
u=fa[top[u]];
}
if(d[u]<d[v])swap(u,v);
ans+=dfn[u]-dfn[v];
return ans;
}
void write(int x)
{
if(x>)write(x/);
putchar(x%+'');
return;
}
int main()
{
//freopen("a.in","r",stdin);
int n=read(),m=read();
tot=;
for(int i=;i<n;++i)
{
int u=read(),v=read();
a[++tot].f=h[u];
h[u]=tot;
a[tot].e=v;
a[++tot].f=h[v];
h[v]=tot;
a[tot].e=u;
}
int s=min(n,);//幸运数赛高！（逃
d[s]=;
dfs(s);
tot=;
dfss(s);
for(int i=;i<=n;++i)
top[i]=fitop(i);
for(int i=;i<=m;++i)
{
int x1=read(),x2=read(),x3=read();
int l1=lca(x1,x2),l2=lca(x2,x3),l3=lca(x1,x3);//两两取lca
int p=dmin(l1,l2,l3);//取最深的为集合点
int ans=dis(x1,p)+dis(x2,p)+dis(x3,p);//算距离，加起来
write(p);
putchar(' ');
write(ans);
putchar('\n');//输出
}
return ;
}