graph

[neal2018]

shrink all circles into points (2-edge-connected-component)

i64 cnt = 0, now = 0;
std::vector<i64> dfn(n, -1), low(n), belong(n, -1), stk;
std::function<void(i64, i64)> tarjan = [&](i64 node, i64 fa) {
  dfn[node] = low[node] = now++, stk.push_back(node);
  for (auto& ne : g[node]) {
    if (ne == fa) continue;  // remove if directed
    if (dfn[ne] == -1) {
      tarjan(ne, node);
      low[node] = std::min(low[node], low[ne]);
    } else if (belong[ne] == -1) {
      low[node] = std::min(low[node], dfn[ne]);
    }
  }
  if (dfn[node] == low[node]) {
    while (true) {
      auto v = stk.back();
      belong[v] = cnt;
      stk.pop_back();
      if (v == node) break;
    }
    ++cnt;
  }
};
tarjan(0, -1);

[neal2018]

2-vertex-connected-component / Block forest

int cnt = 0, now = 0;
vector<vector<ll>> e1(n);
vector<ll> dfn(n, -1), low(n), stk;
function<void(ll)> tarjan = [&](ll node) {
  dfn[node] = low[node] = now++, stk.push_back(node);
  for (auto& ne : g[node]) {
    if (dfn[ne] == -1) {
      tarjan(ne);
      low[node] = min(low[node], low[ne]);
      if (low[ne] == dfn[node]) {
        e1.push_back({});
        while (true) {
          auto x = stk.back();
          stk.pop_back();
          e1[n + cnt].push_back(x);
          // e1[x].push_back(n + cnt); // undirected
          if (x == ne) break;
        }
        e1[node].push_back(n + cnt);
        // e1[n + cnt].push_back(node); // undirected
        cnt++;
      }
    } else {
      low[node] = min(low[node], dfn[ne]);
    }
  }
};

• 0...n-1: circle point (original point)
• n...n+c-1: block point (each stands for one 2-vertex-connected-component)
• articulation point: those with multiple block point as neighbors

jiangly: https://atcoder.jp/contests/abc318/submissions/45146004

[neal2018]

2sat, kosaraju, modified from askd

auto scc(vector<vector<int>>& g) {
  int n = int(g.size()), cnt = 0;
  vector<int> out(n, -1), idx(n, -1), order(n);
  vector<vector<int>> g_inv(n);
  function<void(int)> dfs = [&](int node) {
    out[node] = -2;
    for (auto& ne : g[node]) {
      g_inv[ne].push_back(node);
      if (out[ne] == -1) dfs(ne);
    }
    out[node] = cnt++;
  };
  for (int i = 0; i < n; i++) {
    if (out[i] == -1) dfs(i);
  }
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int u, int v) { return out[u] > out[v]; });
  cnt = 0;
  for (auto i : order) {
    if (idx[i] != -1) continue;
    vector<int> s{i};
    while (!s.empty()) {
      int cur = s.back();
      s.pop_back(), idx[cur] = cnt;
      for (auto& ne : g_inv[cur]) {
        if (idx[ne] == -1) s.push_back(ne);
      }
    }
    cnt++;
  }
  return idx;
}

// 0 => impossible, 1 => possible, 0-based
auto two_sat(int n, vector<array<int, 4>>& clauses) {
  vector<int> res(n);
  vector<vector<int>> g(2 * n);
  for (auto& [x, is_x, y, is_y] : clauses) {
    g[x + is_x * n].push_back(y + (!is_y) * n);
    g[y + is_y * n].push_back(x + (!is_x) * n);
  }
  auto idx = scc(g);
  for (int i = 0; i < n; i++) {
    if (idx[i] == idx[i + n]) return pair{0, res};
    res[i] = idx[i + n] < idx[i];
  }
  return pair{1, res};
}

[neal2018]

2sat, tarjan, modified from jiangly

struct TwoSat {
  int n;
  vector<vector<int>> g;
  vector<bool> res;
  TwoSat(int _n) : n(_n), g(2 * n), res(n) {}
  void add_clause(int u, bool is_u, int v, bool is_v) {
    g[2 * u + !is_u].push_back(2 * v + is_v);
    g[2 * v + !is_v].push_back(2 * u + is_u);
  }
  bool solve() {
    int cnt = 0, now = 0;
    vector<int> dfn(2 * n, -1), low(2 * n), id(2 * n, -1), stk;
    function<void(int)> tarjan = [&](int node) {
      dfn[node] = low[node] = now++, stk.push_back(node);
      for (auto& ne : g[node]) {
        if (dfn[ne] == -1) {
          tarjan(ne);
          low[node] = min(low[node], low[ne]);
        } else if (id[ne] == -1) {
          low[node] = min(low[node], dfn[ne]);
        }
      }
      if (dfn[node] == low[node]) {
        while (true) {
          auto v = stk.back();
          id[v] = cnt;
          stk.pop_back();
          if (v == node) break;
        }
        ++cnt;
      }
    };
    for (int i = 0; i < 2 * n; ++i) {
      if (dfn[i] == -1) tarjan(i);
    }
    for (int i = 0; i < n; ++i) {
      if (id[2 * i] == id[2 * i + 1]) return false;
      res[i] = id[2 * i] > id[2 * i + 1];
    }
    return true;
  }
};

[neal2018]

minimal spanning arborescence

auto edmond(int n, int root, vector<array<int, 3>> edges) {
  constexpr int inf = 1e9;
  int m = int(edges.size());
  int res = 0, max_edge_id = m - 1;
  vector<int> used(m), to_delete(m), to_add(m), edge_id(m);
  iota(edge_id.begin(), edge_id.end(), 0);
  while (true) {
    vector<int> pre(n, -1), seen(n, -1), circle(n, -1), in_edge(n, inf), choose(n);
    in_edge[root] = 0;
    for (int i = 0; i < m; i++) {
      auto& [u, v, w] = edges[i];
      if (u != v && w < in_edge[v]) {
        pre[v] = u, in_edge[v] = w, choose[v] = edge_id[i];
      }
    }
    for (int i = 0; i < n; i++) {
      if (i != root && in_edge[i] == inf) return pair{-1, vector<int>()};
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      res += in_edge[i];
      if (i != root) used[choose[i]]++;
      int v = i;
      for (; seen[v] != i && circle[v] == -1 && v != root; v = pre[v]) seen[v] = i;
      if (v != root && circle[v] == -1) {
        for (; circle[v] != cnt; v = pre[v]) circle[v] = cnt;
        cnt++;
      }
    }
    if (cnt == 0) break;
    for (int i = 0; i < n; i++) {
      if (circle[i] == -1) circle[i] = cnt++;
    }
    for (int i = 0; i < m; i++) {
      auto& [u, v, w] = edges[i];
      int o_v = v;
      u = circle[u], v = circle[v];
      if (u != v) {
        w -= in_edge[o_v];
        used.emplace_back(), to_delete.push_back(choose[o_v]), to_add.push_back(edge_id[i]);
        edge_id[i] = ++max_edge_id;
      }
    }
    n = cnt, root = circle[root];
  }
  for (int i = max_edge_id; i >= m; i--) {
    if (used[i]) used[to_delete[i]]--, used[to_add[i]]++;
  }
  return pair{res, vector<int>(used.begin(), used.begin() + m)};
}

[neal2018]

struct HeavyLight {
  int root = 0, n = 0;
  vector<int> parent, deep, hson, top, sz, dfn;
  HeavyLight(vector<vector<int>>& g, int root)
      : n(int(g.size())), parent(n), deep(n), hson(n, -1), top(n), sz(n), dfn(n, -1) {
    int cur = 0;
    function<int(int, int, int)> dfs = [&](int node, int fa, int dep) {
      deep[node] = dep, sz[node] = 1, parent[node] = fa;
      for (auto &ne : g[node]) {
        if (ne == fa) continue;
        sz[node] += dfs(ne, node, dep + 1);
        if (hson[node] == -1 || sz[ne] > sz[hson[node]]) hson[node] = ne;
      }
      return sz[node];
    };
    function<void(int, int)> dfs2 = [&](int node, int t) {
      top[node] = t, dfn[node] = cur++;
      if (hson[node] == -1) return;
      dfs2(hson[node], t);
      for (auto &ne : g[node]) {
        if (ne == parent[node] || ne == hson[node]) continue;
        dfs2(ne, ne);
      }
    };
    dfs(root, -1, 0), dfs2(root, root);
  }

  int lca(int x, int y) const {
    while (top[x] != top[y]) {
      if (deep[top[x]] < deep[top[y]]) swap(x, y);
      x = parent[top[x]];
    }
    return deep[x] < deep[y] ? x : y;
  };
};

HLD with segtree https://codeforces.com/contest/1878/submission/225728992

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 31;
constexpr int base = 1'000'000'0;

struct Node {
  array<array<int, 2>, 31> info;
  Node(int x = 0, int dep = 0) {
    for (int bit = 0; bit < N; bit++) {
      if (x & (1 << bit)) {
        info[bit] = {dep + base, dep + base};
      } else {
        info[bit] = {-1, -1};
      }
    }
  }
};

Node pull(const Node &a, const Node &b) {
  auto neg_one_min = [](int x, int y) {
    if (x == -1) return y;
    if (y == -1) return x;
    return min(x, y);
  };

  auto neg_one_max = [](int x, int y) {
    if (x == -1) return y;
    if (y == -1) return x;
    return max(x, y);
  };
  Node c;
  for (int bit = 0; bit < N; bit++) {
    c.info[bit] = {neg_one_min(a.info[bit][0], b.info[bit][0]),
                   neg_one_max(a.info[bit][1], b.info[bit][1])};
  }
  return c;
}

Node rev(Node node) {
  for (auto &[x, y] : node.info) {
    swap(x, y);
    if (x != -1) x = 1'000'000 - (x - base);
    if (y != -1) y = 1'000'000 - (y - base);
  }
  return node;
}

struct SegTree {
  ll n;
  vector<Node> t;
  SegTree(ll _n) : n(_n), t(2 * n){};
  void modify(ll p, const Node &v) {
    t[p += n] = v;
    for (p /= 2; p; p /= 2) t[p] = pull(t[p * 2], t[p * 2 + 1]);
  }
  Node query(ll l, ll r) const {
    Node left, right;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) left = pull(left, t[l++]);
      if (r & 1) right = pull(t[--r], right);
    }
    return pull(left, right);
  }
};

struct HeavyLight {
  int root = 0, n = 0;
  vector<int> parent, deep, hson, top, sz, dfn;
  HeavyLight(vector<vector<int>> &g, int _root)
      : root(_root), n(int(g.size())), parent(n), deep(n), hson(n, -1), top(n), sz(n), dfn(n, -1) {
    int cur = 0;
    function<int(int, int, int)> dfs = [&](int node, int fa, int dep) {
      deep[node] = dep, sz[node] = 1, parent[node] = fa;
      for (auto &ne : g[node]) {
        if (ne == fa) continue;
        sz[node] += dfs(ne, node, dep + 1);
        if (hson[node] == -1 || sz[ne] > sz[hson[node]]) hson[node] = ne;
      }
      return sz[node];
    };
    function<void(int, int)> dfs2 = [&](int node, int t) {
      top[node] = t, dfn[node] = cur++;
      if (hson[node] == -1) return;
      dfs2(hson[node], t);
      for (auto &ne : g[node]) {
        if (ne == parent[node] || ne == hson[node]) continue;
        dfs2(ne, ne);
      }
    };
    dfs(root, -1, 0), dfs2(root, root);
  }

  int lca(int x, int y) const {
    while (top[x] != top[y]) {
      if (deep[top[x]] < deep[top[y]]) swap(x, y);
      x = parent[top[x]];
    }
    return deep[x] < deep[y] ? x : y;
  }

  vector<array<int, 2>> get_dfn_path(int x, int y) const {
    array<vector<array<int, 2>>, 2> path;
    bool front = true;
    while (top[x] != top[y]) {
      if (deep[top[x]] > deep[top[y]]) swap(x, y), front = !front;
      path[front].push_back({dfn[top[y]], dfn[y] + 1});
      y = parent[top[y]];
    }
    if (deep[x] > deep[y]) swap(x, y), front = !front;

    path[front].push_back({dfn[x], dfn[y] + 1});
    reverse(path[1].begin(), path[1].end());
    for (const auto &[left, right] : path[1]) path[0].push_back({right, left});
    return path[0];
  }

  Node query_seg(int u, int v, const SegTree &seg) const {
    auto node = Node();
    for (const auto &[left, right] : get_dfn_path(u, v)) {
      if (left > right) {
        node = pull(node, rev(seg.query(right, left)));
      } else {
        node = pull(node, seg.query(left, right));
      }
    }
    return node;
  }
};

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < n - 1; i++) {
      cin >> u >> v, u--, v--;
      g[u].push_back(v), g[v].push_back(u);
    }

    const auto hld = HeavyLight(g, 0);

    auto seg = SegTree(n);
    for (int i = 0; i < n; i++) seg.t[n + hld.dfn[i]] = Node(a[i], hld.deep[i]);
    for (int i = n - 1; i > 0; i--) seg.t[i] = pull(seg.t[i * 2], seg.t[i * 2 + 1]);

    int q;
    cin >> q;
    while (q--) {
      int u, v;
      cin >> u >> v, u--, v--;
      const auto node = hld.query_seg(u, v, seg);
      int addon = 0;
      map<int, int> events;
      for (auto &[x, y] : node.info) {
        if (x != -1) events[x] += 1, events[y + 1] -= 1, addon++;
      }
      int cur = 0, res = 0;
      for (auto &[x, y] : events) {
        cur += y;
        res = max(res, cur);
      }
      cout << res + addon << " ";
    }
    cout << "\n";
  }
}

[neal2018]

virtual tree

map<int, vector<int>> gg;
vector<int> stk{0};
auto add = [&](int x, int y) { gg[x].push_back(y), gg[y].push_back(x); };
for (int i = 0; i < k; i++) {
  if (a[i] != 0) {
    int p = lca(a[i], stk.back());
    if (p != stk.back()) {
      while (dfn[p] < dfn[stk[int(stk.size()) - 2]]) {
        add(stk.back(), stk[int(stk.size()) - 2]);
        stk.pop_back();
      }
      add(p, stk.back()), stk.pop_back();
      if (dfn[p] > dfn[stk.back()]) stk.push_back(p);
    }
    stk.push_back(a[i]);
  }
}
while (stk.size() > 1) {
  if (stk.back() != 0) {
    add(stk.back(), stk[int(stk.size()) - 2]);
    stk.pop_back();
  }
}

[neal2018]

centroid decomposition

vector<char> res(n);
vector<int> seen(n), sz(n);
function<int(int, int)> get_size = [&](int node, int fa) {
  sz[node] = 1;
  for (auto& ne : g[node]) {
    if (ne == fa || seen[ne]) continue;
    sz[node] += get_size(ne, node);
  }
  return sz[node];
};
function<int(int, int, int)> find_centroid = [&](int node, int fa, int t) {
  for (auto& ne : g[node]) {
    if (ne != fa && !seen[ne] && sz[ne] > t / 2) return find_centroid(ne, node, t);
  }
  return node;
};
function<void(int, char)> solve = [&](int node, char cur) {
  get_size(node, -1);
  auto c = find_centroid(node, -1, sz[node]);
  seen[c] = 1;
  res[c] = cur;
  for (auto& ne : g[c]) {
    if (seen[ne]) continue;
    solve(ne, char(cur + 1)); // we can pass c here to build tree
  }
};