summaryrefslogtreecommitdiff
path: root/math/multInv.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'math/multInv.cpp')
0 files changed, 0 insertions, 0 deletions
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-25 00:03:15 +0000
//sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector<vector<int>>& adj, int root) { depth.assign(2 * sz(adj), 0); visited.assign(2 * sz(adj), -1); first.assign(sz(adj), 2 * sz(adj)); idx = 0; dfs(adj, root); st.init(&depth); } void dfs(vector<vector<int>>& adj, int v, ll d=0) { visited[idx] = v, depth[idx] = d; first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { if (first[u] == 2 * sz(adj)) { dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} int getLCA(int u, int v) { if (first[u] > first[v]) swap(u, v); return visited[st.queryIdempotent(first[u], first[v] + 1)]; } ll getDepth(int v) {return depth[first[v]];} };