Tourists Gym - 101002I LCA——dfs+RMQ在线算法

佚名 6年前 (2018-10-04) 算法 1522人围观抢沙发百度已收录

　　LCA（Least Common Ancestors），即最近公共祖先，是指这样一个问题：在有根树中，找出某两个结点u和v最近的公共祖先（另一种说法，离树根最远的公共祖先）。

　　知识需求：1）RMQ的ST算法 2）欧拉序列

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

1）RMQ的ST算法：

　　可以参考我的这篇博客：RMQ原理及实现

2）欧拉序列：

　　所谓欧拉序，就是从根结点出发，按dfs的顺序经过每一个结点最后绕回原点的顺序，比如下面这个例子，欧拉序就是A-B-D-B-E-G-E-B-A-C-F-H-F-C-A

　　那么欧拉序和rmq与LCA有什么关系呢，首先我们知道RMQ可以方便的在线求出区间最小值，以求上图中DG两点最近公共祖先为例，我们先处理出他的欧拉序，我们记录下每个结点第一次被访问的时间，以及每个时间访问的结点编号与结点深度，这时，我们不难发现，D与G第一次出现的时间之间的区域深度最小值就是这两个点对应的最近公共祖先B的深度，我们修改rmq，让其不再返回最小深度，而是返回区间最小深度对应的下标，这里就是求欧拉序中的访问时间，有了这个时间，加上之前的记录，我们可以直接得出该点的编号，从而求出最近公共祖先。

练习题：题目链接

练习题AC代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <vector>
  6 #include <set>
  7 #include <queue>
  8 #include <map>
  9 
 10 using namespace std;
 11 
 12 const int MAXN = 200010 * 2;
 13 
 14 int rmq[MAXN * 2];    //节点深度序列
 15 
 16 struct ST {
 17     int mm[MAXN * 2];
 18     int dp[MAXN][30];
 19     void init(int n) {
 20         mm[0] = -1;
 21         for(int i = 1; i <= n; ++i) {
 22             mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
 23             dp[i][0] = i;
 24         }
 25         for(int j = 1; j <= mm[n]; ++j) 
 26             for(int i = 1; i + (1 << j) - 1 <= n; ++i) 
 27                 dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];
 28     }
 29 
 30     int query(int a, int b) {
 31         if(a > b) swap(a, b);
 32         int k = mm[b - a + 1];
 33         return rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k];
 34     }
 35 };
 36 
 37 struct Edge{
 38     int to, next;
 39 };
 40 
 41 Edge edge[MAXN * 2];
 42 int tot, head[MAXN];
 43 
 44 int F[MAXN * 2];
 45 int P[MAXN];
 46 int cnt;
 47 ST st;
 48  
 49 void init() {
 50     tot = 0;
 51     memset(head, -1, sizeof(head));
 52 }
 53 
 54 void addedge(int u, int v) {
 55     edge[tot].to = v;
 56     edge[tot].next = head[u];
 57     head[u] = tot++;
 58 }
 59 
 60 int d[MAXN];
 61 
 62 void dfs(int u, int pre, int dep) {
 63     d[u] = dep;
 64     F[++cnt] = u;
 65     rmq[cnt] = dep;
 66     P[u] = cnt;
 67     for(int i = head[u]; i != -1; i = edge[i].next) {
 68         int v = edge[i].to;
 69         if(v == pre) continue;
 70         dfs(v, u, dep + 1);
 71         F[++cnt] = u;
 72         rmq[cnt] = dep;
 73     }
 74 }
 75 
 76 void LCA_init(int root, int node_num) {
 77     cnt = 0;
 78     dfs(root, root, 0);
 79     st.init(2 * node_num - 1);
 80 }
 81 
 82 int query_lca(int u, int v) {
 83     return F[st.query(P[u], P[v])];
 84 }
 85 
 86 int main()
 87 {
 88     int T, N, u, v;
 89     scanf("%d", &N);
 90     init();
 91     for(int i = 1; i < N; ++i) {
 92         scanf("%d%d", &u, &v);
 93         addedge(u, v);
 94         addedge(v, u);
 95     }
 96     LCA_init(1, N);
 97 
 98     long long ans = 0;
 99     for(int i = 1; i + i <= N; ++i) {
100         for(int j = i + i; j <= N; j += i) {
101             ans += d[i] + d[j] + 1 - 2 * d[query_lca(i, j)];
102         }
103     }
104     printf("%lld\n", ans);
105     
106     return 0;
107 }