JOI B-聚会 （LCA）题解

这道题，我一看就蒙了，竟然考这样赤裸裸的LCA，我也是醉了。。。
最近公共祖先（LCA）让我们轻而易举地想到了Tarjan+倍增算法来使用。
本人代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=500003,L=19;
int n,m,a,b,c,x,y,z,ans,dp[N],par[N][20];
vector<int> adj[N];
void dfs(int cur,int p){
dp[cur]=dp[p]+1;
par[cur][0]=p;
for(int i=1;i<=L;i++) par[cur][i]=par[par[cur][i-1]][i-1];
for(int u:adj[cur]) if(u!=p)dfs(u,cur);
}
int LCA(int x,int y){//最近公共祖先的函数LCA
if(dp[y]>dp[x]) swap(x,y);
for(int i=L;i>=0;i--) if(dp[par[x][i]]>=dp[y]) x=par[x][i];
if(x==y) return x;
for(int i=L;i>=0;i--) if(par[x][i]!=par[y][i]) x=par[x][i],y=par[y][i];
return par[x][0];
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n-1;i++){
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,0);
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
x=LCA(a,b);
y=LCA(b,c);
z=LCA(a,c);
ans=z;int d=dp[z];
if(dp[x]>d){
ans=x;
d=dp[x];
}
if(dp[y]>d){
ans=y;
d=dp[y];
}
cout<<ans<<" ";
cout<<dp[a]+dp[b]+dp[c]-dp[x]-dp[y]-dp[z]<<endl;
}
}</int>