[洛谷 4281][AHOI2008]紧急集合 / 聚会

题目链接

https://www.luogu.org/problem/P4281

题解

先考虑两个点的情况，显然，树上两点间的最短简单路径一定过这两个点的 LCA。

接下来把结论推广到三个点。我们对这三个点两两求一遍 LCA，会发现其中两个 LCA 位于同一个点。

那么我们将集合点设置为那个单独的 LCA 位置就可以了。

为什么这样是正确的呢？事实上，那个单独的 LCA 位置也是三个 LCA 位置最深的一个，这也就确保了移动距离会尽可能小。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge
{
 int v,next;
}e[1000005];
int head[500005],dep[500005],cnt,fa[500005][25],path[500005];
void addedge(int u,int v)
{
 e[++cnt].v=v;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void dfs(int cur,int d)
{
 dep[cur]=d;
 path[d]=cur;
 for(int i=head[cur];i;i=e[i].next)
  if(dep[e[i].v]==-1)dfs(e[i].v,d+1);
 for(int i=0;(1<<i)<=d;i++)
  fa[cur][i]=path[d-(1<<i)];
 path[d]=0;
 return;
}
int lca(int x,int y)
{
 if(dep[x]>dep[y])swap(x,y);
 for(int i=20;i>=0;i--)
  if(dep[y]-dep[x]-(1<<i)>=0)y=fa[y][i];
 if(x==y)return x;
 for(int i=20;i>=0;i--)
  if(fa[x][i]!=fa[y][i])
  {
   x=fa[x][i];
   y=fa[y][i];
  }
 return fa[x][0];
}
int calc_dep(int x,int y)
{
 return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int main()
{
 int n,m;
 scanf("%d%d",&n,&m);
 memset(dep,-1,sizeof(dep));
 for(int i=1;i<n;i++)
 {
  int x,y;
  scanf("%d%d",&x,&y);
  addedge(x,y);
  addedge(y,x);
 }
 dfs(1,0);
 for(int i=1;i<=m;i++)
 {
  int x,y,z;
  scanf("%d%d%d",&x,&y,&z);
  int l1=lca(x,y),l2=lca(x,z),l3=lca(y,z);
  int ans;
  if(l1==l2)ans=l3;
  else if(l1==l3)ans=l2;
  else ans=l1;
  printf("%d %d\n",ans,calc_dep(ans,x)+calc_dep(ans,y)+calc_dep(ans,z));
 }
 return 0;
}