(\)
(Description)
一棵(N)个节点的树，每条边权都为(1)。
(M)组询问，每次给出三个点(A_i,B_i,C_i)，求从三个点分别出发，移动到同一个点的路径最小权值和。
- (N,Min [1,5 imes10^5])
(\)
(Solution)
-
如果是两个点，显然在两点到(Lca)的路径上任意位置会合都是花费最小的方案。扩展到三个点，我们猜测最优答案也是产生在两点(Lca)或一段路径上。手玩一会样例或者自己造一点数据，可以发现一个事实：三点两两求(Lca)，必然至少有两个(Lca)是同一个点，形象化的表示：
图中所示的是最一般的情况，可以发现两个相同的(Lca)的深度一定不会大于单独的(Lca)的深度，因为相同的(Lca)产生于，单独的(Lca)与不产生这个单独的(Lca)的点求(Lca)。
-
此时方案就显然了，图中所有单色的边是一定要被走一次的，如果在图中的(L2)处会和，双色的边会被(b,c)各走一次，而若在单独的(Lca)处会和，双色的边只会走一次，所以我们直接判断出单独的(Lca)，让第三个点((a))去往那里集合就好，路径长度可以在找(Lca)的时候顺便求出。
(\)
(Code)
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 500010
#define R register
#define gc getchar
using namespace std;
inline int rd(){
int x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
int n,m,t,tot,d[N],hd[N],f[N][20];
struct edge{int to,nxt;}e[N<<1];
inline void add(int u,int v){
e[++tot].to=v; e[tot].nxt=hd[u]; hd[u]=tot;
}
queue<int> q;
inline void bfs(){
q.push(1); d[1]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(R int i=hd[u],v;i;i=e[i].nxt)
if(!d[v=e[i].to]){
d[v]=d[u]+1; f[v][0]=u;
for(R int i=1;i<=t;++i) f[v][i]=f[f[v][i-1]][i-1];
q.push(v);
}
}
}
inline pair<int,int> lca(int u,int v){
int res=0;
if(d[u]>d[v]) u^=v^=u^=v;
for(R int i=t;~i;--i) if(d[f[v][i]]>=d[u]) v=f[v][i],res+=(1<<i);
if(u==v) return make_pair(u,res);
for(R int i=t;~i;--i)
if(f[u][i]!=f[v][i]) v=f[v][i],u=f[u][i],res+=(1<<(i+1));
return make_pair(f[u][0],res+2);
}
int main(){
t=log2(n=rd())+1; m=rd();
for(R int i=1,u,v;i<n;++i){
u=rd(); v=rd(); add(u,v); add(v,u);
}
bfs();
pair<int,int> l1,l2,l3;
for(R int i=1,a,b,c;i<=m;++i){
a=rd(); b=rd(); c=rd();
l1=lca(a,b); l2=lca(a,c); l3=lca(b,c);
if(l1.first==l2.first) printf("%d %d
",l3.first,l3.second+lca(l3.first,a).second);
else if(l1.first==l3.first) printf("%d %d
",l2.first,l2.second+lca(l2.first,b).second);
else if(l2.first==l3.first) printf("%d %d
",l1.first,l1.second+lca(l1.first,c).second);
}
return 0;
}