P4281 [AHOI2008] 紧急集合 / 聚会
不难发现，我们所要求的答案就是一个点，满足它到 \(x,y,z\) 的路径两两无公共边。
在此基础上手玩样例可以发现，\(\text{LCA}(x,y),\text{LCA}(y,z),\text{LCA}(x,z)\) 三个点中，至少有 \(2\) 个点是相等的，且另外那个点作为答案一定最优。
这样我们就能写出代码了，其中 LCA 用了倍增，时间复杂度 \(O((n+m)\log n)\)。如果用 DFS 序来求的话则是 \(O(m+n\log n)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,fa[N][20],idx,d[N],head[N];
struct edge{int nxt,to;}e[N<<1];
void add(int u,int v){e[++idx]={head[u],v},head[u]=idx;}
void dfs(int u,int f){d[u]=d[f]+1;for(int i=0;i<19;i++) fa[u][i+1]=fa[fa[u][i]][i];for(int i=head[u];i;i=e[i].nxt){if(e[i].to!=f) fa[e[i].to][0]=u,dfs(e[i].to,u);}
}
int LCA(int u,int v){if(d[u]<d[v]) swap(u,v);for(int i=19;~i;i--) if(d[fa[u][i]]>=d[v]) u=fa[u][i];if(u==v) return u;for(int i=19;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}
int dis(int x,int y,int lca=0){if(!lca) lca=LCA(x,y);return d[x]+d[y]-2*d[lca];
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v),add(v,u);dfs(1,0);while(m--){int x,y,z;cin>>x>>y>>z;int a[3]{LCA(x,y),LCA(y,z),LCA(x,z)};if(a[0]==a[1]) cout<<a[2]<<" "<<dis(x,z,a[2])+dis(y,a[2])<<"\n";else if(a[0]==a[2]) cout<<a[1]<<" "<<dis(y,z,a[1])+dis(x,a[1])<<"\n";else cout<<a[0]<<" "<<dis(x,y,a[0])+dis(z,a[0])<<"\n";}return 0;
}
我们发现，上面代码中求距离的部分可以合并为一个式子。因为三条路径无公共边，所以答案恒为两两之间距离之和，再 \(\div 2\)，即 d[x]+d[y]+d[z]-d[lca[0]]-d[lca[1]]-d[lca[2]]。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m,fa[N][20],idx,d[N],head[N];
struct edge{int nxt,to;}e[N<<1];
void add(int u,int v){e[++idx]={head[u],v},head[u]=idx;}
void dfs(int u,int f){d[u]=d[f]+1;for(int i=0;i<19;i++) fa[u][i+1]=fa[fa[u][i]][i];for(int i=head[u];i;i=e[i].nxt){if(e[i].to!=f) fa[e[i].to][0]=u,dfs(e[i].to,u);}
}
int LCA(int u,int v){if(d[u]<d[v]) swap(u,v);for(int i=19;~i;i--) if(d[fa[u][i]]>=d[v]) u=fa[u][i];if(u==v) return u;for(int i=19;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1,u,v;i<n;i++) cin>>u>>v,add(u,v),add(v,u);dfs(1,0);while(m--){int x,y,z;cin>>x>>y>>z;int a[3]{LCA(x,y),LCA(y,z),LCA(x,z)},t;if(a[0]==a[1]) t=a[2];else if(a[0]==a[2]) t=a[1];else t=a[0];cout<<t<<" "<<d[x]+d[y]+d[z]-d[a[0]]-d[a[1]]-d[a[2]]<<"\n";}return 0;
}