SGi's Blog

决胜
11月02日（日）
优胜:
准决胜
10月30日（木）				10月31日（金）
优胜: 柊镜(54.9%)				优胜: 柊司(50.9%)
1122		922		1137		1096
准准决胜
10月25日（土）		10月26日（日）		10月27日（月）		10月28日（火）
优胜: 柊镜(59.0%)		优胜: 渚(51.7%)		优胜: 柊司(54.0%)		优胜: 雏菊(55.5%)
1138	790	891	953	1049	894	750	934
C组 代表	D组 代表	E组 代表	F组 代表	G组 代表	A组 代表	B组 代表	H组 代表
柊镜	坂上智代	川添珠姫	古河渚	柊司	伊吹风子	千叶纪梨乃	桂雏菊
幸运☆星	CLANNAD	竹刀少女	CLANNAD	幸运☆星	CLANNAD	竹刀少女	旋风管家

PS：我对日萌绝望了…T T

最近公共祖先（LCA）问题都应该很熟悉了。

LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先

LCA问题可以用朴素的DFS方法解决，但是时间复杂度就很高了，这里介绍一种高级一点的解决LCA问题的Tarjan算法。

Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。

首先需要有一些预备知识：

1.基本图论

这个就不多讲了，如果有不知道的可以随便抓一本数据结构的书恶补一下。

2.并查集

并查集其实也是很简单的东西，实现的代码都不超过10行。

这里提一下并查集的概念，并查集是一种处理元素之间等价关系的数据结构，一开始我们假设元素都是分别属于一个独立的集合里的，主要支持两种操作：

1. 合并两个不相交集合(Union)
2. 判断两个元素是否属于同一集合(Find)

需要知道一点，就是并查集的Find操作的时间复杂度是常数级别的。

考察树T中所有与结点u有关的询问(u, v)

对于子树u中的结点v，满足LCA(u, v) = u

对于子树p1而非子树u中的结点v，满足LCA(u, v) = p1

对于子树p2而非子树p1中的结点v，满足LCA(u, v) = p2

算法DFS有根树T，定义从根节点到当前正在遍历的结点u的路径为活跃路径P
对于每个已经遍历过的结点x，我们用并查集将其连接到P上距离其最近的结点Find(x)

记录与u有关的询问集合为Q(u)

对于Q(u)中的任意一组询问LCA(u, v)，如果v已经遍历过，那么答案就是Find(v)，所以我们只需要维护当前所有以遍历结点的F即可。

第一次遍历结点u时，有Find(u) = u；
遍历完子树u后，子树u内任意结点v均有F(v) = u；回溯回结点p1时，子树u内任意结点v均有F(w) = p1，使用并查集完成即可。

算法流程：

Tarjan(u)
F(u)<-u；
For each (u,v) in Q(u) do Answer(u,v) <- F(v)
For each v in son(u)
a) Tarjan(v)；
b) F(v) <- u；

这里的F用并查集来实现。

这样LCA的Tarjan算法就可以完整的实现了，这个算法的时间复杂度取决于并查集Find操作的时间复杂度，如果采用不相交集森林的方法来实现并查集并采用路径压缩来优化，这样Find操作的时间复杂度可以认为是常数级别的。

所以Tarjan算法的时间复杂度就是O(Na(N) + Q)，a(N)在可以计算的范围内是一个小于4的常数，空间复杂度为O(N)，其中N表示问题规模，Q表示询问次数。

今天水木清华的论坛上有一个很搞笑的题目。大家来看看，如果单凭直觉你会选什么？

在水平地面上，竖直放一个平面镜，一个人站在平面镜前，刚好能在平面镜中看到自己的全身像，当该人向后退的过程中，下列说法正确的是：

A、像将变小，仍能刚好看到自己的全身像 
B、像将变大，看到中间一部分的像，头顶和脚的像看不到了 
C、像的大小不变，仍能刚好看到自己的全身像 
D、像的大小不变，看到自己的全身像，但未占满全幅镜面