| 2 | const int ID = 0; |
| 3 | int f(int a, int b) { return a + b; } |
| 4 | struct HLD { |
| 5 | int n, curhead, curloc; |
| 6 | vi sz, head, parent, loc; |
| 7 | vvi adj; segment_tree values; |
| 8 | HLD(int _n) : n(_n), sz(n, 1), head(n), |
| 9 | parent(n, -1), loc(n), adj(n) { |
| 10 | vector<ll> tmp(n, ID); values = segment_tree(tmp); } |
| 11 | void add_edge(int u, int v) { |
| 12 | adj[u].push_back(v); adj[v].push_back(u); } |
| 13 | void update_cost(int u, int v, int c) { |
| 14 | if (parent[v] == u) swap(u, v); assert(parent[u] == v); |
| 15 | values.update(loc[u], c); } |
| 16 | int csz(int u) { |
| 17 | rep(i,0,size(adj[u])) if (adj[u][i] != parent[u]) |
| 18 | sz[u] += csz(adj[parent[adj[u][i]] = u][i]); |
| 19 | return sz[u]; } |
| 20 | void part(int u) { |
| 21 | head[u] = curhead; loc[u] = curloc++; |
| 22 | int best = -1; |
| 23 | rep(i,0,size(adj[u])) |
| 24 | if (adj[u][i] != parent[u] && |
| 25 | (best == -1 || sz[adj[u][i]] > sz[best])) |
| 26 | best = adj[u][i]; |
| 27 | if (best != -1) part(best); |
| 28 | rep(i,0,size(adj[u])) |
| 29 | if (adj[u][i] != parent[u] && adj[u][i] != best) |
| 30 | part(curhead = adj[u][i]); } |
| 31 | void build(int r = 0) { |
| 32 | curloc = 0, csz(curhead = r), part(r); } |
| 33 | int lca(int u, int v) { |
| 34 | vi uat, vat; int res = -1; |
| 35 | while (u != -1) uat.push_back(u), u = parent[head[u]]; |
| 36 | while (v != -1) vat.push_back(v), v = parent[head[v]]; |
| 37 | u = (int)size(uat) - 1, v = (int)size(vat) - 1; |
| 38 | while (u >= 0 && v >= 0 && head[uat[u]] == head[vat[v]]) |
| 39 | res = (loc[uat[u]] < loc[vat[v]] ? uat[u] : vat[v]), |
| 40 | u--, v--; |
| 41 | return res; } |
| 42 | int query_upto(int u, int v) { int res = ID; |
| 43 | while (head[u] != head[v]) |
| 44 | res = f(res, values.query(loc[head[u]], loc[u]).x), |
| 45 | u = parent[head[u]]; |
| 46 | return f(res, values.query(loc[v] + 1, loc[u]).x); } |
| 47 | int query(int u, int v) { int l = lca(u, v); |
| 48 | return f(query_upto(u, l), query_upto(v, l)); } }; |
| 49 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected