挺好的一道题，本身不难，就把求两个点的LCA变为求三个点两两求LCA，不重合的点才是最优解。值得一提的是，最后对答案的处理运用差分的思想：假设两点 一点深度为d1,另一点
深度为d2,它们LCA深度为d3,这二者之间的距离即为d1+d1-2*d3,只要将这两点推广成三点即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500000
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
int n,m;
long long ans;
int f[maxn+][],dep[maxn+],t;
struct node
{
int from,to,nex;
}edge[*maxn+];
int head[*maxn+],tot=;
inline void add(int x,int y)
{
edge[++tot].from=x;
edge[tot].to=y;
edge[tot].nex=head[x];
head[x]=tot;
}
inline void Deal_first(int u,int father)
{
dep[u]=dep[father]+;
for(int i=;i<=;i++)
{
f[u][i+]=f[f[u][i]][i];
}
for(int e=head[u];e;e=edge[e].nex)
{
int v=edge[e].to;
if(v==father)continue;
f[v][]=u;
Deal_first(v,u);
}
}
inline int LCA(int x,int y)
{
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][];
}
int main()
{
n=read();m=read();
for(int i=;i<=n-;i++)
{
int a,b;
a=read();b=read();
add(a,b);add(b,a);
}
Deal_first(,);
for(int i=;i<=m;i++)
{
ans=;
int a,b,c;
a=read();b=read();c=read();
int t1=LCA(a,b);
int t2=LCA(a,c);
int t3=LCA(b,c);
if(t1==t2)t=t3;
else if(t1==t3)t=t2;
else if(t2==t3)t=t1;
ans=dep[a]+dep[b]+dep[c]-dep[t1]-dep[t2]-dep[t3];
printf("%d %lld\n",t,ans);
}
return ;
}
请各位大佬斧正（反正我不认识斧正是什么意思）