SGi's Blog

You Scored as PoliticalScience/Philosophy

You should strongly consider majoring (or minoring) in Political Science, Philosophy, or related majors (e.g., Criminal Justice, Economics, Geography, History, International Business, Journalism, Sociology, Urban Studies, Women’s Studies). <br> <br> It is possible that the best major for you is your 2nd, 3rd, or even 5th listed category, so be sure to consider ALL majors in your OTHER high scoring categories (below). You may score high in a category you didnt think you would–it is possible that a great major for you is something you once dismissed as not for you. The right major for you will be something 1) you love and enjoy and 2) are really great at it. <br> <br> Consider adding a minor or double majoring to make yourself standout and to combine your interests. Psychology, Sociology, Business Management, French, German, Spanish, Chinese, and Arabic are all great minors for PoliSci majors. Please post your results in your myspace/blog/journal.

Google 2008编程挑战赛已顺利结束，清华大学计算机系的楼天城获得第一名，南京外国语学校的朱泽园获得第二名。进入最终决赛的一百位选手中有19位来自中国。从Google搜索结果来看，楼天城和朱泽园都有过集训参加国际奥林匹克竞赛的经历，其中楼天城与其他两位选手组成清华代表队参加了2007年ACM国际大学生程序设计竞赛，并获得第二名。

膜拜大牛~

最近公共祖先（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表示询问次数。