[AHOI2008]MEET 紧急集合

题意

PS:（最近好多题题意都好难懂啊QAQ）
给你一棵 个节点的树，有 次询问，每个询问给你 三个节点，求树上一个节点使得这三个点到的距离之和最小。每次询问输出这个节点的编号以及路径之和。

分析

考虑每两个节点之间的最短距离就是求这两个点的 ，那么三个点我们可以先两两一组找到 。我们可以发现三个点的 要么是完全一样，要么是有两个（两个相同，一个不同），如果是有两种 那么此时我们要选择不同的那一个这样才能使路径最短，因为可以保证有一条路径不会重复两遍。
就比如下面这张图，如果我们的询问是 那么 的 就是 。的 就是 。的 就是 。此时我们的选择就是 ，因为这样可以少走一次 这条边。完毕

代码

#include<bits/stdc++.h>
#define ll long long
const int N=5e5+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m,cnt;
int head[N],dep[N],fa[N][20],lg[N];
struct node
{
    int nxt,to;
}e[N<<1];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}

void dfs(int x,int fath)                
{
    dep[x]=dep[fath]+1;
    fa[x][0]=fath;
    for(int i=1;i<=lg[dep[x]];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x];i;i=e[i].nxt)
     if(e[i].to!=fath)
      dfs(e[i].to,x);
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y])    swap(x,y);
    while(dep[x]>dep[y])    x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y)    return x;
    for(int i=lg[dep[x]];i>=0;i--)
     if(fa[x][i]!=fa[y][i])
      x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read(),z=read();
        int t1=LCA(x,y),t2=LCA(y,z),t3=LCA(x,z);
        int t;
        if(t1==t2)    t=t3;
        else if(t1==t3)    t=t2;
        else if(t2==t3)    t=t1;
        ll ans=dep[x]+dep[y]+dep[z]-dep[t1]-dep[t2]-dep[t3];        
        printf("%d %lld\n",t,ans);
    }
    return 0;
}