LCA(倍增和tarjan算法)_lca算法模板

---

前言

最近公共祖先简称LCA。两个结点的最近公共祖先就是两个结点的公共祖先中深度最大的结点。

一、LCA一些性质

1、一个结点u的最近公共祖先 lca(u)= u;
2、若u是v的祖先，则 lca(u, v) = u;
3、两点的最近公共祖先必定在树上两点的最短路上。
4、d_min(u, v) = h(u) + h(v) - 2 * h( lca(u, v) );

二、求LCA算法

1.倍增

int fa[N][N]; // fa[i][j]表示结点i的第2^j个祖先
int dep[N]; //记录每个结点的深度
void dfs(int no, int fa) {
    fa[no][0] = fa;
    dep[no] = dep[fa] + 1;
    for (int i = 1; i <= 21; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
    for (int i = he[no]; i != -1; i = nxt[i]) {
        if (to[i] == fa) continue;
        dfs(to[i], no);
    }
}

void lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 21; i >= 0; i--) {
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    }
    if (u == v) return u;
    for (int i = 21; i >= 0; i--) {
        if (fa[u][i] == fa[v][i]) continue;
        u = fa[u][i];
        v = fa[v][i];
    }
    return fa[u][0];
}
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

2.tarjan

struct ed {
    int to;
    int nxt;
    ed():to(0), nxt(-1){}
};
ed e[2 * N];
int he[N];
vector<int> q[N]; //记录查询的边邻接表方式储存
vector<int> id[N];//记录查询编号
vector<int> vis(N, 0);
vector<int> fa(N);
int ans[N];
void unit() {
    iota(fa.begin(), fa.end(), 0);
}
int get(int x) {
    if (x == fa[x]) return fa[x];
    return fa[x] = get(fa[x]);
}
void unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x == y) return;
    fa[y] = x;
}
void add(int u, int v) {
    e[tot].to = v;
    e[tot].nxt = he[u];
    he[u] = tot++;
}
void dfs(int no) {
    vis[no] = 1;
    for (int i = he[no]; i != -1; i = e[i].nxt) {
        int te = e[i].to;
        if (vis[te]) continue;
        dfs(te);
        unite(no, te);
    }
    for (int i = 0; i < q[no].size(); i++) {
        if (vis[q[no][i]] == 2) {
            ans[id[no][i]] = get(q[no][i]);
        }
    }
    vis[no] = 2;
}
void sol() {
    memset(he, -1, sizeof(he));
    int s;
    tot = 0;
    cin >> n >> m >> s;
    unit();
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    int num = 0;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        q[x].push_back(y);
        id[x].push_back(i);
        q[y].push_back(x);
        id[y].push_back(i);
    }
    dfs(s);
    int tag = 0;
    for (int i = 0; i < m; i++) {
        cout << ans[i] << endl;
    }
}
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

题目

LCA模板题洛谷P3379
HDU 2586 how far away?
祖孙查询

//并查集求最大生成树，用倍增维护结点到祖先之间的小值，dp[i][j]表示结点i到第2^j的祖先之间的最小值,dp[i][j] = min(dp[fa[i][j - 1]][j - 1], dp[i][j - 1])).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;
#define fi first
#define se second
const int N = 5e4 + 5;
int n, m;
int fa[10005];
bool vis[N];
void unit() {
    for (int i = 0; i < 10005; i++) fa[i] = i;
}
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    fa[y] = x;
}
bool judge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return true;
    return false;
}

struct ed {
    int to;
    int nxt;
    int w;
};
int he[10005], tot = 0;
ed edge[N];
void add(int u, int v, int w) {
    edge[++tot].to = v;
    edge[tot].nxt = he[u];
    he[u] = tot;
    edge[tot].w = w;
}
int dp[10005][22], dep[10005], pre[10005][22];
void dfs(int no, int num, int w) {
    vis[no] = true;
    dp[no][0] = w;
    pre[no][0] = num;
    dep[no] = dep[num] + 1;
    for(int j = 1; j <= 21; j++) {
        pre[no][j] = pre[pre[no][j - 1]][j - 1];
        dp[no][j] = min(dp[no][j - 1], dp[pre[no][j - 1]][j - 1]);
    }
    for (int j = he[no]; j != -1; j = edge[j].nxt) {
        int te = edge[j].to;
        if (te == num) continue;
        dfs(te, no, edge[j].w);
    }
}
int lca(int u, int v) {
    int ans = inf;
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = 21; j >= 0; j--) {
        if (dep[pre[u][j]] >= dep[v]) {
            ans = min(ans, dp[u][j]);
            u = pre[u][j];
        }
    }
    if (u == v) return ans;
    for (int j = 21; j >= 0; j--) {

        if (pre[u][j] == pre[v][j]) continue;
        else {
            ans = min(ans, dp[u][j]);
            ans = min(ans, dp[v][j]);
            u = pre[u][j], v = pre[v][j];
        }
    }
    ans = min({ans, dp[u][0],dp[v][0]});
    return ans;
}
void sol() {
    memset(dp, inf, sizeof(dp));
    memset(he, -1, sizeof(he));
    memset(dep, 0, sizeof(dep));
    memset(vis, false, sizeof(vis));
    cin >> n >> m;
    vector<int> rank(m);
    iota(rank.begin(), rank.end(), 0);
    vector<pair<int, int>> e(m);
    vector<int> w(m);
    unit();
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        w[i] = z;
        e[i].fi = x, e[i].se = y;
    }
    sort(rank.begin(), rank.end(), [&](const int& a, const int& b) {
        return w[a] > w[b];
        });
    for (auto& x : rank) {
        int u = e[x].fi, v = e[x].se;
        if (judge(u, v)) continue;
        unite(u, v);
        add(u, v, w[x]);
        add(v, u, w[x]);
    }
    int q;
    cin >> q;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        int k = find(i);
        dfs(k, 0, 0);
    }
    while (q--) {
        int u, v;
        cin >> u >> v;
        if (!judge(u, v)) cout << -1 << endl;
        else cout << lca(u, v) << endl;
    }
}
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    sol();
    return 0;
}
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

货车运输
点的距离