POJ 1330 Nearest Common Ancestors [LCA+RMQ]

LCA的入门题，我用的是ST在线算法和Tarjan离线算法。

ST：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <cmath>using namespace std;const int maxn = 10010;int t, n, cnt;vector<int> son[maxn];int parent[maxn];bool vis[maxn];int e[maxn<<1]; // e[]: dfs后的节点序列，int r[maxn]; // r[i]: 节点i在e中第一次出现的位置 int d[maxn<<1]; // d[]: e[]中相应节点的深度 int dp[maxn<<1][16];inline int _min(int i, int j){if (d[i] < d[j]) return i;return j;}void initRMQ(){int nn = 2 * n – 1;for (int i = 0; i < nn; ++i)dp[i][0] = i;int k = (int)(log(nn * 1.0) / log(2.0));for (int j = 1; j <= k; ++j){for (int i = 0; i + (1 << j) – 1 < nn; ++i)dp[i][j] = _min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);}}inline int query(int l, int r){int k = (int)(log(r * 1.0 – l + 1) / log(2.0));return _min(dp[l][k], dp[r-(1<<k)+1][k]);}/*主要过程，求e, r, d数组*/ void dfs(int u, int depth){vis[u] = true;e[cnt] = u;d[cnt] = depth;r[u] = cnt;++cnt;for (int i = 0; i < son[u].size(); ++i){if (!vis[son[u][i]]){dfs(son[u][i], depth + 1);e[cnt] = u;d[cnt++] = depth;}}}int main(){scanf("%d", &t);while (t–){scanf("%d", &n);for (int i = 0; i <= n; ++i){parent[i] = -1;vis[i] = false;son[i].clear();}int u, v, root;for (int i = 1; i < n; ++i){scanf("%d %d", &u, &v);son[u].push_back(v);parent[v] = u;}for (int i = 1; i <= n; ++i){if (parent[i] == -1){root = i;break;}}cnt = 0;dfs(root, 0);initRMQ();scanf("%d %d", &u, &v);if (r[u] <= r[v])printf("%d\n", e[query(r[u], r[v])]);else printf("%d\n", e[query(r[v], r[u])]);}return 0;}

Tarjan：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn = 10010;int t, n;bool vis[maxn];int set[maxn], pre[maxn], an[maxn];vector<int> son[maxn];vector<int> ask[maxn];int find(int x){if (x != set[x])set[x] = find(set[x]);return set[x];}void Union(int x, int y){x = find(x);y = find(y);set[x] = y;}void lca(int x){set[x] = x;an[x] = x;int size = son[x].size();for (int i = 0; i < size; ++i){lca(son[x][i]);Union(x, son[x][i]);an[find(x)] = x;}vis[x] = true;size = ask[x].size();for (int i = 0; i < size; ++i){if (vis[ask[x][i]])printf("%d\n", an[find(ask[x][i])]);}}int main(){scanf("%d", &t);while (t–){scanf("%d", &n);for (int i = 0; i <= n; ++i){pre[i] = -1;vis[i] = false;son[i].clear();ask[i].clear();}int u, v, root;for (int i = 1; i < n; ++i){scanf("%d %d", &u, &v);son[u].push_back(v);pre[v] = u;}for (int i = 1; i <= n; ++i){if (pre[i] == -1){root = i;break;}}scanf("%d %d", &u, &v);ask[u].push_back(v);ask[v].push_back(u);lca(root);}return 0;}

，一个人行走，若是寂寞了，寻一座霓虹灯迷离闪烁，