Algoogle

Algorithm for Programming Contest

HL分解

基本情報


計算量(構築)
計算量(LCA)

N := 頂点数

解説


木のパスを重さごとに分割する.
ある頂点vから伸びる重い辺とは, vの子のうち部分木の大きさがが最大の頂点への辺のこと.
これによって作られる連続するHeavy-Edgeをまとめて列として扱うことができる.
各辺集合をSegment-Treeで管理することが多い.
Heavy-Light Decompositionがよくまとまっている.

コード


(hl-decomposition.cpp) download
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
namespace HLD {
const int N = 200010;
vector<vector<int>> chains, childs;
int V, dep[N], par[N], heavy[N], head[N], chain[N], id[N], size[N], q[N];

void calc_heavy() {
    int root = -1;
    childs.assign(V,vector<int>());
    for(int v = 0; v < V; v++) {
        size[v] = 0;
        heavy[v] = -1;
        if(par[v] < 0) root = v;
        else childs[par[v]].push_back(v);
    }
    int l = 0, r = 0;
    q[r++] = root;
    while(l < r) {
        int v = q[l++];
        for(auto &w: childs[v]) {
            if(w == par[v]) continue;
            dep[w] = dep[v]+1;
            q[r++] = w;
        }
    }
    reverse(q,q+V);
    for(int i = 1; i < V; i++) {
        int v = q[i], &u = par[v];
        size[u] += ++size[v];
        if(heavy[u] == -1 or size[v] > size[heavy[u]]) heavy[u] = v;
    }
}
void calc_chain() {
    chains.clear();
    int idx = 0;
    for (int v = 0; v < V; v++) {
        if(par[v] < 0 or heavy[par[v]] != v) {
            chains.push_back(vector<int>());
            for (int w = v; w != -1; w = heavy[w]) {
                chain[w] = idx;
                head[w] = v;
                id[w] = chains.back().size();
                chains.back().push_back(w);
            }
            idx++;
        }
    }
}
void make_par(const vector<vector<int>> &g, int root = 0) {
    memset(par,-1,sizeof(par));
    par[root] = 0;
    int l = 0, r = 0;
    q[r++] = root;
    while(l < r) {
        int v = q[l++];
        for(const int &w: g[v]) if(par[w] < 0) q[r++] = w, par[w] = v;
    }
    par[root] = -1;
}
void build(const vector<vector<int>> &g, int root = 0) {
    V = g.size();
    make_par(g,root);
    calc_heavy();
    calc_chain();
}
int lca(int u, int v) {
    while (chain[u] != chain[v]) {
        if (dep[head[u]] > dep[head[v]]) swap(u,v);
        v = par[head[v]];
    }
    return dep[u] < dep[v]? u: v;
}
}

問題


Comments