【寻找中点】

题目描述

Windy 和 Zero 居住在同一个国家,该国家有N个城市。Windy 居住在 X 城市,Zero 居住在 Y 城市。任意两个城市之间有且只有一条路径相通(中间可能经过其它城市)。有一天,Windy 和 Zero 想见面,他们想把见面的地点定在城市 X 和城市 Y 的中间。现在请你告诉他们会见地点应该在哪里?

输入格式

第一行是一个整数 N(1≤N≤10 000),表示有 N 个城市。
接下来有 N-1 行,每行有两个整数 A,B,表示有一条路直接连接城市 A 和城市 B。
(1≤A,B≤N)
接下来有一个整数 M(1≤M≤100 000),表示下面有 M 个询问。
接下来有 M 行,每行有两个整数 X,Y,表示 Windy 和 Zero 居住的城市编号。
(1≤X,Y≤N)

输出格式

对于每个询问,如果城市 X 和城市 Y 的中点在一个城市上,则输出该中点城市的编号;如果这个中点在某条路径上,则输出这条路径两个端点的城市编号(用一个空格隔开),并且首先输出离城市X近的城市的编号。

样例数据 1

输入

6
1 2
2 3
2 4
4 5
6 4
3
5 3
3 5
6 5

输出

4 2
2 4
4

备注

【样例图示】

嘛…… LCA模板题 具体的题解:

本题题意是,给定一棵最多10000个结点的树,以及最多100000个询问。对于每个询问中要查询的两个结点,输出它们之间路径上的中点;特别地,如果这个中点在某条边上,则输出这条边的两个端点。注意这里说的路径是简单路径,也就是不能经过重复的边和点。
考虑单个询问的情况,给定任意的两个结点x和y,我们可以从x或y出发,进行一次深度优先搜索,即可知道x到y的路径及其长度,这样很容易就可以知道其中点。但是这样对于每个询问的复杂度都是O(N)的,对于本题N=10000个点以及M=100000个询问来说,这样的复杂度也是不可以接受的。
回顾树的性质,我们可以知道,一棵树上任意两个结点之间有且只有一条简单路径。而对于一棵有根树,任意两个结点之间则最少存在一个公共的祖先。不妨记根结点的深度为0,根结点的儿子结点深度为1,孙子结点深度为2,以此类推可以得到所有结点的深度。在这个基础上,我们可以定义任意两个结点x和y之间的最近公共祖先(Least common Ancestors),简称LCA(x,y)。一个结点是结点x和y的LCA当且仅当它是两者的深度最大的公共祖先(也就是离x和y最近)。不难发现,LCA(x,y)一定在x和y之间的路径上,而且从x走到y的话,必定是先往上走到LCA,再马上从LCA往下走。这说明,如果我们事先求出所有结点的深度,并能快速地求出所有结点对的LCA,则所有结点对的路径长度很容易就能知道。接下来我们还可以发现,运用适当的求LCA的方法,则我们也可以快速地求出路径的中点来。
求LCA有很多种算法,这里我们只介绍一种在线的倍增算法。这种算法依靠一个操作Ancetor(x,H),这个操作是用来在O(logH)中求结点x的深度差为H的祖先。首先我们需要定义一个二维数组A,A[x,i]代表与x深度相差2i的祖先。不难发现A满足一个性质:
A[x,i+1]=A[A[x,i],i]
因此,我们可以通过从根结点开始的深度优先搜索顺序,在O(NlogN)的时间内预处理生成整个A数组。接下来通过A来求任意的 Ancetor(x,H)。不妨设j是使2j≤H成立的最大非负整数,则我们有:
Ancetor(x,H)=Ancetor(A,[x,j],H-2j])
所以我们可以通过递归的方法来计算 Ancetor(x,H),而H最多收敛logH次即可变为0,因此在O(logH)的时间复杂度我们就可以算出任意的Ancetor(x,H)。
有了A数组,用类似Ancetor(x,H)的方法,我们现在可以计算任意结点对x和y的LCA。不妨设x深度不小于y。显然有
LCA(x,y)=LCA(Ancestor(x,deep(y) – deep(x)),y)。
这里deep(x)代表x深度。令x’=Ancestor(x,deep(y)- deep(x)),若x’=y,则LCA(x’,y)=y;否则令i是使A[x’,i]≠A[y,i]成立的最大非负整数,则必定有
LCA(x’,y)=LCA(Ancestor(x’,i),Ancestor(y,i))。
故通过递归的方法也可以在O(logN)的时间来算出任意的LCA(x,y)。
利用Ancestor(x,H)和LCA(x,y)操作,我们可以得到求任意的x到Y的路径的中点。首先求出LCA(x,y),查找x和y以及LCA(x,y)的深度,即可知道x到y的路径的长度L。若x深度较大,则输出Ancestor(x,L/2),如果L为奇数,则还需要输出Ancestor(x,L/2+1)。反之,则相应地输出Ancestor(Y,L/2+1)和Ancestor(y,L/2)即可。
最后来分析以上算法的复杂度。预处理A数组需要O(Nlog2N)的时间,每个查询需要O(log2N)的复杂度,故整个算法的时间复杂为O((N+M)log2N)。空间方面,存储A数组需要O(Nlog2N)的空间,存放其他信息需要O(N)的空间,因此空间复杂度为O(Nlog2N)。

据说还有迷之Tarjan离线算法,不过目前还没看过,嗯直接上在线的代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*