分类 最近公共祖先 下的文章

BZOJ 1776: [Usaco2010 Hol]cowpol 奶牛政坛

Description农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上,标号为1到N。恰好有N-1条单位长度的双向道路,用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说,这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合,详细说明了每个草地的父节点P_i (0 <= P_i <= N)。根节点的P_i == 0, 表示它没有父节点。因为奶牛建立了1到K一共K (1 <= K <= N/2)个政党。每只奶牛都要加入某一个政党,其中, 第i只奶牛属于第A_i (1 <- 阅读剩余部分 -

BZOJ 1787: [Ahoi2008]Meet 紧急集合

题目描述输入输出样例输入6 4 1 2 2 3 2 4 4 5 5 6 4 5 6 6 3 1 2 4 4 6 6 6样例输出5 22 54 16 0提示题解首先把无根树随便以一个点为根转换成有根树。对于三个点两两求 LCA,通过画图可以归纳出,必定有两个 LCA 是一样的,那剩下的另一个 LCA 就是所求的咯。简单证明下,假设三个点深度不同且不在一条链上,那么必然有深度最小的一个点,很显然这个点与深度较大的两个点的 LCA 都是一样的。假设我们只求深度最小和最大,这两个点的集合地点,很明显,他们两个点路径上的任何点都可以,如果加入深度次小的一个点,它要想连到这条路径上,显- 阅读剩余部分 -

【最近公共祖先】BZOJ 1602: [Usaco2008 Oct]牧场行走

题目描述N头牛(2<=n<=1000)别人被标记为1到n,在同样被标记1到n的n块土地上吃草,第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走,第i条边连接第Ai,Bi块牧场,第i条边的长度是Li(1<=Li<=10000)。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况,所以说这是一棵树。 这些奶牛是非常喜欢交际的,经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。输入第一行:两个被空格隔开的整数:N和Q第二行到第n行:第i+1行有两个被空格隔开的整数:AI,BI,- 阅读剩余部分 -