Distance Queries
LCA问题:
LCA:Least Common Ancestors(最近公共祖先),对于一棵有根树T的任意两个节点u,v,求出LCA(T, u, v),即离跟最远的节点x,使得x同时是u和v的祖先。
在线算法:用比较长的时间做预处理,但是等信息充足以后每次回答询问只需要用比较少的时间。
离线算法:先把所有的询问读入,然后一起把所有询问回答完成。
在线算法:用比较长的时间做预处理,但是等信息充足以后每次回答询问只需要用比较少的时间。
离线算法:先把所有的询问读入,然后一起把所有询问回答完成。
下面这个博客有LCA问题的介绍,以及Tarjin 和 RMQ 算法的介绍。
Tarjin (离线算法)
Tarjin算法是离线算法,先获得所有询问,然后统一处理,利用DFS + 并查集实现。
Tarjan算法处理某一个节点X的过程分为这么几步:
1、建立只有一个X节点的集合。也就是在并查集里,root[X] = X,并且标记该节点已经访问。
2、处理所有关于X的询问,对于(X, Y),如果Y已经处理过,那么LCA(X, Y) = find(Y),也就是Y在并查集里的根节点。如果Y没有处理过,忽略这个询问。
要处理所有询问,必须将(X,Y)这个询问分别加到X和Y结点上。
1、建立只有一个X节点的集合。也就是在并查集里,root[X] = X,并且标记该节点已经访问。
2、处理所有关于X的询问,对于(X, Y),如果Y已经处理过,那么LCA(X, Y) = find(Y),也就是Y在并查集里的根节点。如果Y没有处理过,忽略这个询问。
要处理所有询问,必须将(X,Y)这个询问分别加到X和Y结点上。
3、递归这个过程处理X的孩子。
4、将root[X]设为father[X],也就是X的父亲。
4、将root[X]设为father[X],也就是X的父亲。
伪代码:
//parent为并查集,FIND为并查集的查找操作 2 Tarjan(u) 3 visit[u] = true 4 for each (u, v) in QUERY 5 if visit[v] 6 ans(u, v) = FIND(v) 7 for each (u, v) in TREE 8 if !visit[v] 9 Tarjan(v) 10 parent[v] = u
下面的博客关于Tarjin算法解释的比较清楚。
DFS + RMQ (在线算法)
LCA算法可以转化为RMQ算法:
(1)DFS:从树T的根开始,进行深度优先遍历,并记录下每次到达的顶点。第一个的结点是root(T),每经过一条边都记录它的端点。由于每条边恰好经过2次,因此一共记录了2n-1个结点,用E[1, ... , 2n-1]来表示。
在DFS的过程中,同时记录下每个顶点的深度。用depth[]记录。
在DFS的过程中,记录下第一次到达该顶点的数组下标。
(2)计算R:用R[i]表示E数组中第一个值为i的元素下标,即如果R[u] < R[v]时,DFS访问的顺序是E[R[u], R[u]+1, ..., R[v]]。虽然其中包含u的后代,但深度最小的还是u与v的公共祖先。
(3)RMQ:当R[u] ≥ R[v]时,LCA[T, u, v] = RMQ(L, R[v], R[u]);否则LCA[T, u, v] = RMQ(L, R[u], R[v]),计算RMQ。
由于RMQ中使用的ST算法是在线算法,所以这个算法也是在线算法。
(2)计算R:用R[i]表示E数组中第一个值为i的元素下标,即如果R[u] < R[v]时,DFS访问的顺序是E[R[u], R[u]+1, ..., R[v]]。虽然其中包含u的后代,但深度最小的还是u与v的公共祖先。
(3)RMQ:当R[u] ≥ R[v]时,LCA[T, u, v] = RMQ(L, R[v], R[u]);否则LCA[T, u, v] = RMQ(L, R[u], R[v]),计算RMQ。
由于RMQ中使用的ST算法是在线算法,所以这个算法也是在线算法。
题目大意:
求一棵树上两个节点(u,v)之间的最短距离,用LCA取出最近公共祖先root。则最短距离为 dis[u] + dis[v] - 2 * dis[root]。其中dis为每个节点到根节点的距离。
Tarjin 算法:
/* Tarjin 离线算法 struct node { int x, d; }; int n, m, dis[maxn], ans[maxn], vis[maxn] = {0}, f[maxn]; vector<node> V[maxn], query[maxn]; void init() { scanf("%d%d", &n, &m); int a, b; char ch; node tmp; for (int i = 0; i < m; i++) { scanf("%d%d%d %c", &a, &b, &tmp.d, &ch); tmp.x = b; V[a].push_back(tmp); tmp.x = a; V[b].push_back(tmp); } scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%d%d", &a, &b); tmp.d = i, tmp.x = b; query[a].push_back(tmp); tmp.x = a; query[b].push_back(tmp); } } int find(int x) { if (f[x] != x) f[x] = find(f[x]); return f[x]; } void dfs(int u, int d) { vis[u] = 1, f[u] = u, dis[u] = d; for (int i = 0; i < query[u].size(); i++) if (vis[query[u][i].x]) { int v = query[u][i].x, w = query[u][i].d; ans[w] = dis[u] + dis[v] - 2 * dis[find(v)]; } for (int i = 0; i < V[u].size(); i++) if (!vis[V[u][i].x]) { int v = V[u][i].x, w = V[u][i].d; dfs(v, d + w); f[v] = u; } } int main () { init(); dfs(1, 0); for (int i = 0; i < m; i++) printf("%d\n", ans[i]); return 0; } */
DFS + RMQ 算法:
//DFS + RMQ 在线算法 struct node { int x, d; }; vector<node> V[maxn]; int E[maxn * 2], D[maxn * 2], first[maxn], vis[maxn], dis[maxn], n, m, top = 1; int dp[30][maxn * 2]; void init() { scanf("%d%d", &n, &m); int a, b; char ch; node tmp; for (int i = 0; i < m; i++) { scanf("%d%d%d %c", &a, &b, &tmp.d, &ch); tmp.x = b; V[a].push_back(tmp); tmp.x = a; V[b].push_back(tmp); } } void dfs(int u, int dep, int w) { vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++, dis[u] = w; for (int i = 0; i < V[u].size(); i++) if (!vis[V[u][i].x]) { int v = V[u][i].x, cost = V[u][i].d; dfs(v, dep + 1, w + cost); E[top] = u, D[top++] = dep; } } void ST(int num) { for (int i = 1; i <= num; i++) dp[0][i] = i; for (int i = 1; i <= log2(num); i++) for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num) { int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)]; if (D[a] < D[b]) dp[i][j] = a; else dp[i][j] = b; } } int RMQ(int x, int y) { int k = (int) log2(y - x + 1.0); int a = dp[k][x], b = dp[k][y - (1 << k) + 1]; if (D[a] < D[b]) return a; return b; } int main () { init(); dfs(1, 0, 0); ST(top - 1); scanf("%d", &m); int x, y; while(m--) { scanf("%d%d", &x, &y); int a = first[x], b = first[y]; if (a > b) swap(a, b); int pos = RMQ(a, b); printf("%d\n", dis[x] + dis[y] - 2 * dis[E[pos]]); } return 0; }