文件名称：LCA的tarjan算法
文件大小：2KB
文件格式：CPP
更新时间：2012-08-27 03:35:53
POJ 1470 （Closest Common Ancestors）
对于LCA问题，有不少解法，这儿提供了tarjan算法，这是一种离线算法，读入所有输入然后一并处理，并且利用并查集的思想，从根节点开始DFS，对每一个DFS的节点，先把他的父亲节点指向本身，没访问完一个子节点，然后把该子节点的父亲指向该节点，当所有子节点DFS完毕后，将该节点标记为已访问，然后对和该节点有关的询问进行处理，如果另一个节点未被标记则跳过，否则这次询问的结果即是另一个节点的代表元（刘汝佳黑书里介绍很详细）