POJ 1330 Nearest Common Ancestors(LCA，在线处理三种方式)

题目链接：
POJ 1330 Nearest Common Ancestors
题意：
给一个$n$点和$n-1$条边的树，第$n$行是要查询的两个节点的最近公共祖先，输出要查询的最近公共祖先。
数据范围：$n\leq 10^{4}$
分析：
可以学习《挑战程序设计竞赛》$P_{328}-P_{331}$

暴力求解

记节点$v$到根的深度为$depth[v]$。那么如果节点$w$是$u$和$v$的公共祖先的话，让$u$向上走$depth[u]-depth[w]$步，让$v$向上走$depth[v]-depth[w]$步，都将走到$w$。因此，首先让$u$和$v$中较深的一个向上走$|depth[u]-depth[v]|$步，再一起一步步向上走，直到走到同一个节点即是$LCA$。
时间复杂度：$dfs$:$O(n)$,单次查询：$O(n)$

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 10010;int T, n, total, root;
int head[MAX_N], in[MAX_N], fa[MAX_N], depth[MAX_N];struct Edge {int v, next;
}edge[MAX_N];void AddEdge(int u, int v) 
{edge[total].v = v;edge[total].next = head[u];head[u] = total++;
}void dfs(int u, int p, int cur)
{fa[u] = p;depth[u] = cur;for (int i = head[u]; i != -1; i = edge[i].next) {dfs (edge[i].v, u, cur + 1);}
}int LCA(int u, int v)
{while (depth[u] > depth[v]) u = fa[u];while (depth[v] > depth[u]) v = fa[v];while (u != v) {u = fa[u];v = fa[v];}return u;
}int main()
{scanf("%d", &T);while (T--) {total = 0;memset(head, -1, sizeof (head));memset(in, 0, sizeof (in));scanf("%d", &n);int u, v;for (int i = 1; i <= n; ++i) {scanf("%d%d", &u, &v);if (i != n) {AddEdge(u, v);in[v]++;}}for (int i = 1; i <= n; ++i) {if (in[i] == 0) {root = i;break;}}dfs (root, -1, 0);printf("%d\n", LCA(u, v));}return 0;
}

二分搜索

首先对于任意节点$v$，利用其父节点$parent[v][1]$信息，可以通过$parent[v][2]=parent[parent[v][1]][1]$得到其向上走两步所到的节点，再利用这一信息，又可以通过$parent[v][4]=parent[parent[v][2]][2]$得到其向上走四步所到的节点。依此类推，就能够得到其向上走$2^k$步所到的节点$parent[v][k]$。有了$k=floor(log_{2}(n))$以内的所有信息后，就可以二分搜索了。
预处理$parent[v][k]$：$O(n\log n)$，单次查询：$O(\log n)$

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;
const int MAX_N = 10010;
const int MAX_LOG_N = 20; // MAX_LOG_N = log2(MAX_N)int T, n, total, root;
int head[MAX_N], in[MAX_N], depth[MAX_N], fa[MAX_N][MAX_LOG_N];struct Edge {int v, next;
}edge[MAX_N];void AddEdge(int u, int v)
{edge[total].v = v;edge[total].next = head[u];head[u] = total++;
}void dfs(int u, int p, int d)
{ // 获取每个节点的深度和直接父亲depth[u] = d;fa[u][0] = p;for (int i = head[u]; i != -1; i = edge[i].next) {dfs(edge[i].v, u, d + 1);}
}void RMQ() // 时间复杂度: O(nlog(n))
{ // 倍增处理每个节点的祖先for (int k = 0; k + 1 < MAX_LOG_N; ++k) { for (int i = 1; i <= n; ++i) {if (fa[i][k] == -1) fa[i][k + 1] = -1;else fa[i][k + 1] = fa[fa[i][k]][k];}}   
}int LCA(int u, int v) // 时间复杂度：O(log(n))
{ // 先把两个节点提到同一深度if (depth[u] > depth[v]) swap(u, v);for (int k = 0; k < MAX_LOG_N; ++k) {if (((depth[v] - depth[u]) >> k) & 1) {v = fa[v][k];}}if (u == v) return v;// 二分搜索计算LCAfor (int k = MAX_LOG_N - 1; k >= 0; --k) {if (fa[u][k] != fa[v][k]) {u = fa[u][k];v = fa[v][k];}}return fa[u][0];
}int main()
{scanf("%d", &T);while (T--) {memset(head, -1, sizeof (head));memset(in, 0, sizeof(in));memset(depth, 0, sizeof(depth));memset(fa, -1, sizeof(fa));total = 0;scanf("%d", &n);int u, v;for (int i = 1; i <= n; ++i) {scanf("%d%d", &u, &v);if (i != n) {AddEdge(u, v);in[v]++;}}// 找到根节点for (int i = 1; i <= n; ++i) { if (in[i] == 0) {root = i;break;}}dfs(root, -1, 0);RMQ();printf("%d\n", LCA(u, v));}return 0;
}

基于RMQ的算法

其实上面的二分搜索算法已经有了$RMQ$的意思了。
将树转为从根$DFS$标号后得到的序列处理。
首先按从根$DFS$访问的顺序得到顶点序列$vis[i]$和对应的深度$depth[i]$。对于每个顶点$v$，记其在$vis[]$中首次出现的下标为$id[v]$。而$LCA(u,v)$就是访问$u$之后到访问$v$之前所经过的节点中离根最近的那个，假设$id[u]\leq id[v]$，那么有：

$$LCA(u,v)=vis[k],其中k是所有id[u]\leq i \leq id[v]中depth[i]最小的i$$
预处理： $O(n\log n)$，单次查询： $O(1)$

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 10010;int T, n, total;
int head[MAX_N], vis[MAX_N * 2], id[MAX_N], depth[MAX_N * 2], dp[MAX_N * 2][20], in[MAX_N];struct Edge {int v, next;
} edge[MAX_N * 2];void AddEdge (int u, int v)
{edge[total].v = v;edge[total].next = head[u];head[u] = total++;
}void dfs(int u, int p, int d, int& k)
{vis[k] = u; // dfs访问顺序id[u] = k; // 节点在vis中首次出现的下标depth[k++] = d; // 节点对应的深度for (int i = head[u]; i != -1; i = edge[i].next) {int v = edge[i].v;if (v == p) continue;dfs(v, u, d + 1, k); // 递归访问子节点vis[k] = u; // 再次访问depth[k++] = d; // 标记vis的深度}
}void RMQ(int root) // 处理区间深度最小值,保存最小值的下标
{ // 就是区间左右端点最近公共祖先的下标，即：vs[Min] = LCAint k = 0;dfs(root, -1, 0, k);// printf ("k = %d\n", k);int m = k; // m = 2 * n - 1int e = (int)(log2(m + 1.0)); // 区间长度m + 1for (int i = 0; i < m; ++i) dp[i][0] = i;for (int j = 1; j <= e; ++j) {for (int i = 0; i + (1 << j) - 1 < m; ++i) {int nxt = i + (1 << (j - 1));if (depth[dp[i][j - 1]] < depth[dp[nxt][j - 1]]) {dp[i][j] = dp[i][j - 1];} else {dp[i][j] = dp[nxt][j - 1];}}}
}int LCA(int u, int v)
{int left = min(id[u], id[v]), right = max(id[u], id[v]);int k = (int)(log2(right - left + 1.0)); // 区间长度，注意用log2！int pos, nxt = right - (1 << k) + 1; // nxt 分界点if (depth[dp[left][k]] < depth[dp[nxt][k]]) {pos = dp[left][k];} else {pos = dp[nxt][k];}return vis[pos];
}int main()
{scanf("%d", &T);while (T--) {memset(head, -1, sizeof(head));memset(in, 0, sizeof(in));total = 0;int u, v;scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d%d", &u, &v);if (i < n) {AddEdge(u, v);in[v]++;}}int root;for (int i = 1; i <= n; ++i) {if (in[i] == 0) {root = i;break;}}RMQ(root);printf("%d\n", LCA(u, v));}return 0;
}