Class HLD_naive

code/graph/hld.test.cpp:3–76

#include "../code/data-structures/union_find.cpp"

struct HLD_naive {
  int n;
  vector<vii> adj;
  vii parent;

  HLD_naive(int _n) : n(_n), adj(n), parent(n, ii(-1, ID)) { }

  void add_edge(int u, int v) {
    adj[u].push_back(ii(v, ID));
    adj[v].push_back(ii(u, ID));
    parent[v] = ii(u, ID);
  }

  void update_cost(int u, int v, int c) {
    if (parent[v].first == u)
      swap(u, v);

    assert(parent[u].first == v);
    parent[u] = ii(v, c);

    for (int i = 0; i < size(adj[u]); i++)
      if (adj[u][i].first == v)
        adj[u][i] = ii(v, c);

    for (int i = 0; i < size(adj[v]); i++)
      if (adj[v][i].first == u)
        adj[v][i] = ii(u, c);
  }

  int lca(int u, int v) {
    vi uat, vat; int res = -1;
    while (u != -1) uat.push_back(u), u = parent[u].first;
    while (v != -1) vat.push_back(v), v = parent[v].first;
    u = (int)size(uat) - 1, v = (int)size(vat) - 1;
    while (u >= 0 && v >= 0 && uat[u] == vat[v])
      res = uat[u], u--, v--;
    return res;
  }

  // int query_upto(int u, int v) {

  // }

  int query(int u, int v) {
    // int l = lca(u, v);
    // return f(query_upto(u, l), query_upto(v, l));

    vector<bool> visited(n, false);
    stack<ii> S;
    S.push(ii(u, ID));
    visited[u] = true;

    while (!S.empty())
    {
      ii cur = S.top(); S.pop();
      // printf("%d\n", cur.first);

      if (cur.first == v)