lca
题意:求3个点的lca,以及3个点与lca的距离之和。
性质:设点q1,q2,q3
两点之间的lca
t1=lca(q1,q2)
t2=lca(q1,q3)
t3=lca(q2,q3)
一定有两个lca重合
3个点的公共lca一定在 两个lca之间(有重合)
而重合的lca深度必定更浅
所以3个点的公共lca就是那个不重合的lca
(完整证明还是看题解吧TAT)
使用倍增法(懒得打树剖了qwq)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
template <typename T> inline void read(T &x){
char c=getchar(); x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=(x<<)+(x<<)+(c^),c=getchar();
}
template <typename T> inline void output(T x){
if(!x) {putchar(); return ;}
int wt[],l=;
while(x) wt[++l]=x%,x/=;
while(l) putchar(wt[l--]+);
}
int n,m,ans,fa[][],d[];
int cnt,hd[],nxt[],ed[],poi[]; //注意边开2倍
inline void add(int x,int y){
nxt[ed[x]]=++cnt; hd[x]= hd[x] ? hd[x]:cnt;
ed[x]=cnt; poi[cnt]=y;
}
inline void dfs(int x,int _fa){
d[x]=d[_fa]+; fa[][x]=_fa;
for(int i=;(<<i)<=d[x];++i) fa[i][x]=fa[i-][fa[i-][x]];
for(int i=hd[x];i;i=nxt[i]) if(poi[i]!=_fa) dfs(poi[i],x);
}
inline int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
for(int i=;i>=;--i) if(d[fa[i][x]]>=d[y]) x=fa[i][x];
if(x==y) return x;
for(int i=;i>=;--i) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[][x];
}
//----------lca模板---------
int main(){
read(n); read(m); int q1,q2,q3;
for(int i=;i<n;++i) read(q1),read(q2),add(q1,q2),add(q2,q1);
dfs(,);
for(int i=;i<=m;++i){
read(q1),read(q2),read(q3); ans=;
int t1=lca(q1,q2);
int t2=lca(q1,q3);
int t3=lca(q2,q3);
if(t1==t2) ans=t3;
else if(t1==t3) ans=t2;
else if(t2==t3) ans=t1; //找到不同的那个lca
output(ans),putchar(' ');
output(d[q1]+d[q2]+d[q3]-d[t1]-d[t2]-d[t3]),putchar('\n');
}return ;
}