洛谷P4281：https://www.luogu.org/problemnew/show/P4281
思路
答案所在的点必定是三个人所在点之间路径上的一点
本蒟蒻一开始的想法是：先求出2个点之间的LCA 再求出此LCA和第3个点的LCA
但是没有考虑到有可能答案所在点可能比2个点之间的LCA深度更深
因为两点之间的LCA是两点共同能到达的深度最浅的一个点
所以我们可以考虑：
设a=LCA(x,y) 此时x和y到a点为最小花费 则此时z到a的花费可以用LCA(a,z)来计算
因此我们分别计算3种情况并取最小值即可
设d为树的深度 a为x和y的LCA b为a与z的LCA 从x到a y到a 分别花费d[x]-d[a]和d[y]-d[a] 从z到a花费d[z]+d[a]-2*d[b]
则ans=max(d[x]+d[y]+d[z]-d[a]-2*d[b])
代码
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 500050
#define INF 1e9+7
int n,m,cnt,ans,a,b,k,x,y,z;
int h[maxn],dep[maxn],f[maxn][];
struct Edge
{
int next;
int to;
}e[maxn<<];
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=h[u];
h[u]=cnt;
}
void deal(int u,int fa)//常规预处理
{
dep[u]=dep[fa]+;
for(int i=;i<=;i++)
{
f[u][i]=f[f[u][i-]][i-];
}
for(int i=h[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa) continue;
f[v][]=u;
deal(v,u);
}
}
int lca(int x,int y)//常规LCA
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=;i>=;i--)
{
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
}
for(int i=;i>=;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][];
}
void check()
{
int t=dep[x]+dep[y]+dep[z]-dep[a]-*dep[b];//计算每种情况的ans
if(t<ans)//如果当前值小于原ans 则替换
{
ans=t;
k=a;//k为最后的位置
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
deal(,);//预处理
for(int i=;i<=m;i++)
{
ans=INF;//初始化
scanf("%d%d%d",&x,&y,&z);
a=lca(x,y);//三种情况分别计算
b=lca(a,z);
check();
a=lca(x,z);
b=lca(a,y);
check();
a=lca(z,y);
b=lca(a,x);
check();
printf("%d %d\n",k,ans);
}
}