diff options
Diffstat (limited to 'graph/hld.cpp')
| -rw-r--r-- | graph/hld.cpp | 32 |
1 files changed, 14 insertions, 18 deletions
diff --git a/graph/hld.cpp b/graph/hld.cpp index 9431782..7e3331f 100644 --- a/graph/hld.cpp +++ b/graph/hld.cpp @@ -1,35 +1,31 @@ vector<vector<int>> adj; vector<int> sz, in, out, nxt, par; -int t; +int counter; void dfs_sz(int v = 0, int from = -1) { - sz[v] = 1; - for (auto& u : adj[v]) { - if (u != from) { - dfs_sz(u, v); - sz[v] += sz[u]; - } + for (auto& u : adj[v]) if (u != from) { + dfs_sz(u, v); + sz[v] += sz[u]; if (adj[v][0] == from || sz[u] > sz[adj[v][0]]) { swap(u, adj[v][0]); }}} void dfs_hld(int v = 0, int from = -1) { par[v] = from; - in[v] = t++; - for (int u : adj[v]) { - if (u == from) continue; - nxt[u] = (u == adj[v][0] ? nxt[v] : u); + in[v] = counter++; + for (int u : adj[v]) if (u != from) { + nxt[u] = (u == adj[v][0]) ? nxt[v] : u; dfs_hld(u, v); } - out[v] = t; + out[v] = counter; } -void init() { +void init(int root = 0) { int n = sz(adj); - sz.assign(n, 0); in.assign(n, 0); out.assign(n, 0); - nxt.assign(n, 0); par.assign(n, -1); - t = 0; - dfs_sz(); dfs_hld(); + sz.assign(n, 1), nxt.assign(n, 0), par.assign(n, -1); + in.resize(n), out.resize(n); + counter = 0; + dfs_sz(root); dfs_hld(root); } vector<pair<int, int>> get_intervals(int u, int v) { @@ -47,6 +43,6 @@ vector<pair<int, int>> get_intervals(int u, int v) { int get_lca(int u, int v) { while (true) { if (in[v] < in[u]) swap(u, v); - if (in[nxt[v]] <= in[u]) return in[u]; + if (in[nxt[v]] <= in[u]) return u; v = par[nxt[v]]; }} |