思路:这道题是一个树结构,并且点的个数只有三个,因此我们需要考虑三个点之间可能存在的关系。从两个点(a,b)的情况入手,我们会发现:树中的点c只要位于a~b的路径上一定是最短距离。现在再引入一个点,我们发现其实三个点两两之间都有一个lca,但最终有一个点会重叠,因此只有两个点满足条件,我们选择深度较深的点作为答案.最终输出结果即可.
# include<iostream>
# include<cstring>
# include<algorithm>
using namespace std;
const int N = 500010,M = 1000010,MAXN = 20;
int h[N],e[M],ne[M],idx;
int depth[N],f[N][MAXN];
int n,m;
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}
// lca预处理
void dfs(int u,int fa){
depth[u] = depth[fa] + 1;
f[u][0] = fa;
for(int j=1;j<19;++j){
f[u][j] = f[f[u][j-1]][j-1];
}
for(int i=h[u];i!=-1;i=ne[i]){
int j = e[i];
if(j == fa) continue;
dfs(j,u);
}
}
// 求lca
int lca(int x,int y){
if(depth[x] < depth[y]){
swap(x,y);
}
for(int i=19;i>=0;--i){
if(depth[f[x][i]] >= depth[y]){
x = f[x][i];
}
}
if(x == y) return x;
for(int i=19;i>=0;--i){
if(f[x][i] != f[y][i]){
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
int main(){
memset(h,-1,sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dfs(1,0);
// 树上问题 很显然考虑两个点之间的lca 如果在lca位置一定到两个点的距离是最短的
while(m --){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
int a = lca(x,y),b = lca(x,z),c = lca(y,z);
if(a == b) swap(a,c);
if(depth[a] < depth[b]) swap(a,b);
// 此时a是深度最大的点 b是深度次大的点
int sum = depth[x] + depth[y] + depth[z] - 2 * depth[b] - depth[a];
printf("%d %d\n",a,sum);
}
return 0;
}