题解【[AHOI2008]紧急集合 / 聚会】

题解【[AHOI2008]紧急集合 / 聚会】"/>

题解【[AHOI2008]紧急集合 / 聚会】

简化版题目：

有一棵 N N N个节点的树，和 Q Q Q组询问

有三个人分别在点 x , y , z x,y,z x,y,z现在希望你找到一个点，使得
三个人到这个点的距离和最小。

题目分析

首先，本题最大的难度就是求的是三条路径的最小值，而不是两个，如果是两个的话我们直接求书的路径上的点就行，即为求两点之间的 L C A LCA LCA，但是如果问题为 3 3 3的点就不同了，我们类比之前，可能会想到求出 3 3 3个点的 L C A LCA LCA，可是这样，明显是不对的，比如下边这幅图就是一个反例。

         ·A/  \/    \/      \.C        .B/ \/   \.D    .E

若在此图中寻找一个点，使其到 B , E , F B,E,F B,E,F之和最小，显然不是求三者 L C A − A LCA-A LCA−A点,而是应当选 C C C点，这样他们的值才能最小。

为什么这么说呢？可以把 B B B翻转过来，然后就可以发现应该在他们的交点 C C C上可以取到最小值。

这道题还有一个情况如下

         .A//C./ \/   \.B    \D.

现在我们要求 B , C , D B,C,D B,C,D的最短距离，我们怎么走。

这其实是最简单的一种模型。肯定是走在 B B B时最短。

然后我们发现，无论这棵树有多么复杂，一共就这两种雏形的情况。

然后开始我们找规律时间

• 1 1 1：我们发现，三个点两两之间的 L C A LCA LCA一定有两个点相同

• 2 2 2:如果只有两个点相同，那么聚集点就一定是剩下一个 L C A LCA LCA

• 3 3 3:如果 3 3 3个点的 L C A LCA LCA都相同，那么聚集点就是这个 L C A LCA LCA

其实上述的推理得到的结论就是：找两两之间 L C A LCA LCA深度最深的一个

于是这个问题就这样解决了，时间复杂度为 O ( N O(N O(N l o g log log N ) N) N)

关于 L C A LCA LCA,因为我太菜了，我用的是倍增求 L C A LCA LCA。当然也可以用别的方法

参考代码如下

#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#define N 500001
using namespace std;
int n,m,id[N],cnt,fa[N][21],p,deep[N],tmp;
int front[N],next[N*2],to[N*2],tot;
int lca1,lca2,lca3;
template<class T> inline void read(T &x)
{x=0;register char c=getchar();register bool f=0;while (!isdigit(c)) f ^=c=='-',c=getchar();while (isdigit(c)) x=x*10+c-'0',c=getchar();if(f)x=-x;
}
template <class T> inline void print(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar('0'+x%10);
}
void add(int x,int y)
{to[++tot]=y; next[tot]=front[x]; front[x]=tot;to[++tot]=x; next[tot]=front[y]; front[y]=tot;
}
void dfs(int x)
{id[x]=++cnt;for(int i=front[x];i;i=next[i])if(to[i]!=fa[x][0]) {fa[to[i]][0]=x;deep[to[i]]=deep[x]+1;dfs(to[i]);}
}
int lca(int x,int y)
{if(x==y) return x;if(id[x]<id[y]) swap(x,y);for(int i=p;i>=0;i--)if(id[fa[x][i]]>id[y])x=fa[x][i];return fa[x][0];
}
int dis(int x,int y)
{int lc=lca(x,y);return deep[x]+deep[y]-2*deep[lc];
}
int main()
{read(n);read(m);int x,y,z;for(int i=1;i<n;i++){read(x);read(y);add(x,y);}dfs(1);p=log(n)/log(2)+1;for(int j=1;j<=p;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];int ans1,ans2,tmp;while(m--){read(x);read(y);read(z);lca1=lca(x,y); lca2=lca(x,z); lca3=lca(y,z);ans1=lca1; ans2=dis(x,lca1)+dis(y,lca1)+dis(z,lca1);tmp=dis(x,lca2)+dis(y,lca2)+dis(z,lca2);if(tmp<ans2) {ans2=tmp;ans1=lca2;}tmp=dis(x,lca3)+dis(y,lca3)+dis(z,lca3);if(tmp<ans2){ans2=tmp;ans1=lca3;}printf("%d %d\n",ans1,ans2);}
}