题目链接: https://ac.nowcoder.com/acm/problem/20532

简化题意

在一棵树上，找到一个点，使得这个点到给定的3个点的距离和最小

分析

图片说明
问：先考虑简化题目，如果只给定2个点求距离之和最小应该这么做？
答：sb题，直接一个LCA模板就行辣，集合点就在2点之间的最短路径上
问：那么如何求LCA呢
答：倍增求呗，如果被卡常了还可以用树链剖分求LCA
问：具体点，倍增这么求LCA？
答：
那首先要知道倍增是什么

倍增就是 “成倍增加” 的意思，比如 1 倍增后变成了 2，2 倍增后就变成了 4，4 变成 8，以此类推...

考虑暴力求LCA

两个点先到达同一深度，然后一直往上跳父亲，知道两个点跳到同一个点上，这个点就是 LCA。

暴力求复杂度是o(n)的，如果询问多了就凉凉
由于暴力是一个一个跳的，我们可以一次性跳多次
具体可以参见此博客： https://www.cnblogs.com/Kaike/p/12312896.html
问：解决了这些基础知识，可以开始本题了吗？
答：可以了
问：请开始你的表演
答：
首先这个题的点数从两个变成了3个
我们把连接3个点的边单独提取出来
如果3个开始不共点
那么提取出的图中有且只有一个点的度为3
这个点就是我们需要的汇点
考虑这个点的性质，我们可以发现这个点是属于3个点两两组合后的LCA
但是3个点两两组合后的LCA会有多个点
我们发现这个汇点是深度最深的LCA点
判断一下，我们就找到了汇点
接下来求距离就简单了
此题完

参考代码

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,m;
struct oppo{
    int to,nex;
}rod[N*2];
int head[N],tot;
void add(int from,int to)
{
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int dep[N];
int fa[N][22];
void dfs(int x,int father)
{
    fa[x][0]=father;
    dep[x]=dep[father]+1;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(to==father) continue;
        dfs(to,x);
    }
}
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];
}
void work()
{
    dep[0]=-1;
    dfs(1,0);
    for(int k=1;k<=20;k++)
        for(int i=1;i<=n;i++)
            fa[i][k]=fa[ fa[i][k-1] ][k-1];
}
int dis(int x,int y)
{
    return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int s,t;
        scanf("%d%d",&s,&t);
        add(s,t);
        add(t,s);
    }
    work();
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        int LCA=0;
        int l1=lca(a,b),l2=lca(b,c),l3=lca(a,c);
        if(dep[l1]>dep[LCA]) LCA=l1;
        if(dep[l2]>dep[LCA]) LCA=l2;
        if(dep[l3]>dep[LCA]) LCA=l3;
        if(LCA==l1) printf("%d %d\n",LCA,dep[a]+dep[b]-2*dep[LCA]+dis(LCA,c));
        else if(LCA==l2) printf("%d %d\n",LCA,dep[b]+dep[c]-2*dep[LCA]+dis(LCA,a));
        else if(LCA==l3) printf("%d %d\n",LCA,dep[a]+dep[c]-2*dep[LCA]+dis(LCA,b));
    }
    return 0;
}