NC20532. [AHOI2008]MEET 紧急集合
描述
欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有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
输出:
5 2 2 5 4 1 6 0
C++(clang++11) 解法, 执行用时: 763ms, 内存消耗: 70176K, 提交时间: 2020-11-29 11:52:10
#include <stdio.h>
#include <algorithm>
using namespace std;
int dep[500010],fa[500010][21];
int head[500010],nex[1000010],ver[1000010],tot;
void add(int u,int v)
{
nex[++tot]=head[u];
ver[tot]=v;
head[u]=tot;
}
void dfs(int u)
{
for(int i=head[u];i;i=nex[i])
{
int v=ver[i];
if(dep[v])continue;
dep[v]=dep[u]+1;fa[v][0]=u;
for(int j=1;j<=20;j++)fa[v][j]=fa[fa[v][j-1]][j-1];
dfs(v);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;i--)
{
if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
}
if(x==y)return x;
for(int i=20;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dep[1]=1;
dfs(1);
int ans;
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int x,y,z;
x=lca(a,b),y=lca(b,c),z=lca(a,c);
if(x==y)ans=z;
else if(x==z)ans=y;
else if(y==z)ans=x;
printf("%d %d\n",ans,dep[a]+dep[b]+dep[c]-dep[x]-dep[y]-dep[z]);
}
}