题解【[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);}
}
更多推荐
题解【[AHOI2008]紧急集合 / 聚会】
发布评论