POJ 1470 Cloest Common Ancestor(用Tarjan查询LCA)

题目链接；
POJ 1470 Cloest Common Ancestor
题意：
给一个$n$个节点，$n-1$条边的树，有多组查询两个节点的最近公共最先，按编号从小到大输出至少作为一次查询的最近公共祖先的节点编号和相应的次数。
数据范围：$n\leq 900$
分析：
$Tarjan$离线处理。当然使用基于$RMQ$的在线处理方式也应该可以
。

算法从根节点$root$开始搜索，每次递归搜索所有的子树，然后处理跟当前根节点相关的所有查询。
用集合表示一类节点，这些节点跟集合外的点的$LCA$都一样，并把这个$LCA$设为这个集合的祖先。当搜索到节点$x$时，创建一个由$x$本身组成的集合，这个集合的祖先为$x$自己。然后递归搜索$x$的所有儿子节点。当一个子节点搜索完毕时，把子节点的集合与$x$节点的集合合并，并把合并后的集合的祖先设为$x$。因为这棵子树内的查询已经处理完，$x$的其他子树节点跟这棵子树节点的$LCA$都是一样的，都为当前根节点$x$。所有子树处理完毕之后，处理当前根节点$x$相关的查询。遍历$x$的所有查询，如果查询的另一个节点$v$已经访问过了，那么$x$和$v$的LCA即为$v$所在集合的祖先。
其中关于集合的操作都是使用并查集高效完成。
算法的复杂度为，$O(n)$搜索所有节点，搜索每个节点时会遍历这个节点相关的所有查询。如果总的查询个数为$Q$，则总的复杂度为$O(n+Q)$。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
typedef long long ll;
const int MAX_N = 1010;
const int MAX_M = 500010;int n, m;
int in[MAX_N], fa[MAX_N], cnt[MAX_N], vis[MAX_N], ancestor[MAX_N];
// fa[]:并查集操作，cnt[i]:i作为LCA的次数，vis[]:标记是否访问，ancestor[]:存集合的LCA
vector<int> vec[MAX_N], query[MAX_N]; 
// vec[i]:存i指向节点（儿子）信息，query[i]:存需要查i和谁的LCAint find(int x)
{return fa[x] == x ? x : fa[x] = find(fa[x]);
}void Union(int x, int y)
{int fx = find(x), fy = find(y);if (fx != fy) {fa[fy] = fx;}
}void Tarjan(int x)
{for (int i = 0; i < vec[x].size(); ++i) {Tarjan(vec[x][i]);Union(x, vec[x][i]); // 注意传参和并查集合并顺序}vis[x] = 1;for (int i = 0; i < query[x].size(); ++i) {if (vis[query[x][i]]) { // x 和 query[x][i]的LCA是find(query[x][i])cnt[find(query[x][i])]++;}}
}void init()
{for (int i = 0; i <= n; ++i) {fa[i] = ancetor[i] = i;vec[i].clear();query[i].clear();}memset(vis, 0, sizeof(vis));memset(in, 0, sizeof(in));memset(cnt, 0, sizeof(cnt));
}int main()
{while (~scanf("%d", &n)) {init();for (int i = 1; i <= n; ++i) {int u, num, v;scanf("%d:(%d)", &u, &num);for (int j = 0; j < num; ++j) {scanf("%d", &v);vec[u].push_back(v);in[v]++;}}scanf("%d", &m);while (m --) {while(getchar() != '(') ;int u, v;scanf("%d%d", &u, &v);query[u].push_back(v);query[v].push_back(u);}while (getchar() != ')') ;// 找到根节点int root;for (int i = 1; i <= n; ++i) {if (in[i] == 0) {root = i;break;}}Tarjan(root);for (int i = 1; i <= n; ++i) {if (cnt[i]) printf("%d:%d\n", i, cnt[i]);}}return 0;
}