LCA学习笔记

发表于 | 更新于 | 分类于 | 热度： ℃

LCA学习笔记

祖先的定义

如果学习树结构就会明白除了根节点以外每个节点都有一个父节点，所以我们定义祖先为父节点的父节点，然后我们给出最近公共祖先的定义

一棵树祖先中到两个点距离最近的节点。

能够解决LCA问题的方式有很多，所以作为一个ACM选手，肯定是我全都要

解决方案

欧拉序

树的欧拉序是对树进行dfs的一种序列，他有两条性质

  • 在每个节点进和出都加入序列
  • 只要到达每一个节点就把他加入序列

那么我们寻找他们的最近公共祖先就可以从第一次出现第一个节点和第一次出现的第二个节点之间节点中深度最大的节点。

HDOJ[2586]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define pb push_back
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 4e4+200;
const int maxm = 2e2+10;
int dis[maxn];
int n,m;
struct node{
    int next,to,val;
}G[maxn<<1];
int head[maxn];
int cnt;
vector<int> order;
void init(){
    cnt = 0;
    memset(head,-1,sizeof(head));
    order.clear();
}
void add(int u,int v,int val){
    G[cnt].next = head[u];
    G[cnt].to = v;
    G[cnt].val = val;
    head[u] = cnt++;
}
void dfs(int u,int fa,int val){
    order.pb(u);
    dis[u] = val;
    for(int i=head[u];~i;i=G[i].next){
        int v = G[i].to;
        if(v==fa) continue;
        dfs(v,u,val+G[i].val);
        order.pb(v);
    }
}
int find(int p1,int p2){
    int mmin = INF,res;
    if(p1>p2){
        int temp = p1;
        p1 = p2;
        p2 = temp;
    }
    rep(i,p1,p2+1){
        if(dis[order[i]] < mmin){
            mmin = dis[order[i]];
            res = i;
        }
    }
    return res+1;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        init();
        rep(i,0,n-1){
            int u,v,val;
            scanf("%d%d%d",&u,&v,&val);
            add(u,v,val); add(v,u,val);
        }
        dfs(1,1,0);
        int len = order.size();
        rep(i,0,m){
            int x,y; int p1=-1,p2=-1;
            scanf("%d%d",&x,&y);
            rep(j,0,len){
                if(p1==-1&&x==order[j]) p1 = j;
                if(p2==-1&&y==order[j]) p2 = j;
                if(p1!=-1 && p2!=-1) break;
            }
            int lca = find(p1,p2);
            //cout<<dis[lca]<<' '<<dis[x]<<' '<<dis[y]<<endl;
            int ans = dis[x]-dis[lca]+dis[y]-dis[lca];
            printf("%d\n",ans);
        }

    }

    return 0;
}

Trajan算法

首先Trajan是一个离线算法，在一次遍历中把所有询问一次解决，时间复杂度$O(n+q)$。

大佬题解

我也想自己写啊，但是就是不会啊，自己想是不可能自己想的，只要抄抄别人的博客才能维持生活。

  1. 任选择一个点作为根节点，从根节点开始
  2. 遍历该节点的所有子节点，并标记这些子节点$v$已经被访问过
  3. 如果$v$还有子节点，返回2，否则就进入下一步
  4. 合并$v$到$u$。
  5. 寻找与当前点$u$有询问关系的点$v$
  6. 若是$v$已经被访问过了，则可以确定$u$和$v$的最近公共祖先为$v$被合并的父亲节点$fa[u]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int T,n,cnt;
const int maxn = 1e4+10;
struct node{
    int next,to;
}G[maxn<<1];
int head[maxn],fa[maxn],vis[maxn],ans[maxn];
void init(){
    cnt = 0;
    memset(head,-1,sizeof(head));
    memset(fa,0,sizeof(fa));
    memset(vis,0,sizeof(vis));
    rep(i,1,n+1) fa[i] = i;
}
void add(int u,int v){
    G[cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt++;
}
int find(int x){
    if(fa[x]!=x) fa[x] = find(fa[x]);
    return fa[x];
}
struct Query{
    int to,id;
    Query(){}
    Query(int _to,int _id){
        to = _to;
        id = _id;
    }
};
vector<Query> query[maxn];
void dfs(int now){
    int u,v;
    vis[now] = 1;
    for(int i=head[now];~i;i=G[i].next){
        v = G[i].to;
        if(vis[v]) continue;
        dfs(v);
        fa[v] = now;
    }
    for(int i = 0;i<query[now].size();i++){
        Query node = query[now][i];
        u = node.to; int id = node.id;
        if(vis[u] == 2){
            ans[find(u)] ++;
        }
    }
    vis[now] = 2;
}
int vvis[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    while(~scanf("%d",&n)){
    memset(head,-1,sizeof(head));
    cnt = 0;
    memset(vis,0,sizeof(vis));
    memset(vvis,0,sizeof(vvis));
    memset(ans,0,sizeof(ans));
    rep(i,1,n+1) query[i].clear();
    rep(i,1,n+1) fa[i] = i;
    int root = 0;
    rep(i,0,n){
        int u,x,v;scanf("%d",&u);
        scanf("%*c%*c%d%*c",&x);
        rep(i,0,x){
            scanf("%d",&v);
            add(u,v);
            vvis[v] = 1;
        }
    }
    rep(i,1,n+1){
        if(vvis[i]==0){
            root = i;
            break;
        }
    }
    int m;scanf("%d",&m);
    char ch;
    rep(i,0,m){
        ch = getchar();
        while(ch!='(') ch = getchar();
        int u,v;scanf("%d%d",&u,&v);
        query[u].push_back(Query(v,i));
        query[v].push_back(Query(u,i));
        while(ch!=')') ch = getchar();
    }
    dfs(root);
    rep(i,1,n+1){
        if(ans[i]){
            printf("%d:%d\n",i,ans[i]);
        }
    }
    }
    return 0;
}

RMQ算法(ST表)

其实这个方法也就是欧拉序加上RMQ，在第一个解决方案中我们使用枚举来寻找他们的LCA，这也导致时间复杂度变成了$O(n^2)$。而寻找固定区间内的最小值是一个很普遍的问题，也就是RMQ。而解决RMQ有很多种$O(logn)$的方法，

  • 线段树、树状数组
  • ST表

他们均可以有效地解决区间最值问题。

例题[hdoj5044]

使用方法为 RMQ+正负tag

详情见我刷的LCA专题训练。

Reference:https://blog.csdn.net/czl_233/article/details/78368927

http://www.cppblog.com/menjitianya/archive/2015/12/10/212447.html

http://www.cnblogs.com/JVxie/p/4854719.html