hld

ソースコード

  1#pragma once
  2
  3#include <vector>
  4#include <stack>
  5using namespace std;
  6
  7// HLD
  8namespace titan23 {
  9
 10    class HLD {
 11      public:
 12        vector<vector<int>> G;
 13        int root, n;
 14        vector<int> size, par, dep, nodein, nodeout, head, hld;
 15
 16      private:
 17        void _dfs() {
 18            dep[root] = 0;
 19            stack<int> st;
 20            st.emplace(~root);
 21            st.emplace(root);
 22            while (!st.empty()) {
 23                int v = st.top(); st.pop();
 24                if (v >= 0) {
 25                    int dep_nxt = dep[v] + 1;
 26                    for (const int x: G[v]) {
 27                        if (dep[x] != -1) continue;
 28                        dep[x] = dep_nxt;
 29                        st.emplace(~x);
 30                        st.emplace(x);
 31                    }
 32                } else {
 33                    v = ~v;
 34                    for (int i = 0; i < (int)G[v].size(); ++i) {
 35                        int x = G[v][i];
 36                        if (dep[x] < dep[v]) {
 37                            par[v] = x;
 38                            continue;
 39                        }
 40                        size[v] += size[x];
 41                        if (size[x] > size[G[v][0]]) {
 42                            swap(G[v][0], G[v][i]);
 43                        }
 44                    }
 45                }
 46            }
 47
 48            int curtime = 0;
 49            st.emplace(~root);
 50            st.emplace(root);
 51            while (!st.empty()) {
 52                int v = st.top(); st.pop();
 53                if (v >= 0) {
 54                    if (par[v] == -1) {
 55                        head[v] = v;
 56                    }
 57                    nodein[v] = curtime;
 58                    hld[curtime] = v;
 59                    ++curtime;
 60                    if (G[v].empty()) continue;
 61                    int G_v0 = (int)G[v][0];
 62                    for (int i = (int)G[v].size()-1; i >= 0; --i) {
 63                        int x = G[v][i];
 64                        if (x == par[v]) continue;
 65                        head[x] = (x == G_v0? head[v]: x);
 66                        st.emplace(~x); 
 67                        st.emplace(x); 
 68                    }
 69                } else {
 70                    nodeout[~v] = curtime;          
 71                }
 72            }
 73        }
 74
 75      public:
 76        HLD() {}
 77        HLD(const vector<vector<int>> &G, const int root) :
 78                G(G), root(root), n(G.size()),
 79                size(n, 1), par(n, -1), dep(n, -1),
 80                nodein(n, -1), nodeout(n, -1), head(n, -1), hld(n, -1) {
 81            _dfs();
 82        }
 83
 84        template<typename T>
 85        vector<T> build_list(vector<T> a) const {
 86            vector<T> res(a.size());
 87            for (int i = 0; i < n; ++i) {
 88                res[i] = a[hld[i]];
 89            }
 90            return res;
 91        }
 92
 93        //! `u`, `v` の lca を返す / `O(logn)`
 94        int lca(int u, int v) const {
 95            while (true) {
 96                if (nodein[u] > nodein[v]) swap(u, v);
 97                if (head[u] == head[v]) return u;
 98                v = par[head[v]];
 99            }
100        }
101
102        //! `s` から `t` へ、`k` 個進んだ頂点を返す / `O(logn)`
103        int path_kth_elm(int s, int t, int k) {
104            int x = lca(s, t);
105            int d = dep[s] + dep[t] - 2*dep[x];
106            if (d < k) return -1;
107            if (dep[s] - dep[x] < k) {
108                s = t;
109                k = d - k;
110            }
111            int hs = head[s];
112            while (dep[s] - dep[hs] < k) {
113                k -= dep[s] - dep[hs] + 1;
114                s = par[hs];
115                hs = head[s];
116            }
117            return hld[nodein[s] - k];
118        }
119
120        vector<pair<int, int>> for_each_vertex_path(int u, int v) const {
121            vector<pair<int, int>> res;
122            while (head[u] != head[v]) {
123                if (dep[head[u]] < dep[head[v]]) swap(u, v);
124                res.emplace_back(nodein[head[u]], nodein[u]+1);
125                u = par[head[u]];
126            }
127            if (dep[u] < dep[v]) swap(u, v);
128            res.emplace_back(nodein[v], nodein[u]+1);
129            return res;
130        }
131
132        pair<int, int> for_each_vertex_subtree(int v) const {
133            return {nodein[v], nodeout[v]};
134        }
135    };
136}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/hld.cpp