Hld

struct Hld {
  int n;
  std::vector<int> siz;
  std::vector<int> top;
  std::vector<int> dep;
  std::vector<int> par;
  std::vector<int> tin;
  std::vector<int> tout;
  std::vector<int> order;
  std::vector<std::vector<int>> adj;

  explicit Hld(int n) {
    this->n = n;
    siz.resize(n, 1);
    top.resize(n);
    dep.resize(n);
    par.resize(n);
    tin.resize(n);
    tout.resize(n);
    order.resize(n);
    adj.resize(n);
  }

  [[nodiscard]] const std::vector<int>& operator[](int index) const {
    assert(0 <= index && index < n);
    return adj[index];
  }

  void addEdge(int u, int v) {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    assert(u != v);
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  void work(int root = 0) {
    assert(0 <= root && root < n);
    top[root] = root;
    par[root] = -1;
    {
      auto dfs = [&](auto&& dfs, int u) -> void {
        for (auto& v : adj[u]) {
          adj[v].erase(std::find(adj[v].begin(), adj[v].end(), u));
          par[v] = u;
          dep[v] = dep[u] + 1;
          dfs(dfs, v);
          siz[u] += siz[v];
          if (siz[v] > siz[adj[u][0]]) {
            std::swap(v, adj[u][0]);
          }
        }
      };
      dfs(dfs, root);
    }
    {
      int timer = 0;
      auto dfs = [&](auto&& dfs, int u) -> void {
        tin[u] = timer++;
        order[tin[u]] = u;
        for (auto& v : adj[u]) {
          top[v] = (v == adj[u][0] ? top[u] : v);
          dfs(dfs, v);
        }
        tout[u] = timer;
      };
      dfs(dfs, root);
    }
  }

  [[nodiscard]] int getLca(int u, int v) const {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]]) {
        u = par[top[u]];
      } else {
        v = par[top[v]];
      }
    }
    return dep[u] < dep[v] ? u : v;
  }

  template <typename F>
  void applyOnPath(int u, int v, bool root, F&& func) const {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    while (top[u] != top[v]) {
      if (dep[top[u]] > dep[top[v]]) {
        func(tin[top[u]], tin[u] + 1, false);
        u = par[top[u]];
      } else {
        func(tin[top[v]], tin[v] + 1, true);
        v = par[top[v]];
      }
    }
    if (root) {
      if (dep[u] < dep[v]) {
        func(tin[u], tin[v] + 1, true);
      } else {
        func(tin[v], tin[u] + 1, false);
      }
    } else {
      if (u != v) {
        if (dep[u] < dep[v]) {
          func(tin[u] + 1, tin[v] + 1, true);
        } else {
          func(tin[v] + 1, tin[u] + 1, false);
        }
      }
    }
  }

  [[nodiscard]] int getDist(int u, int v) const {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    return dep[u] + dep[v] - 2 * dep[getLca(u, v)];
  }

  [[nodiscard]] int jump(int u, int k) const {
    assert(0 <= u && u < n);
    if (dep[u] < k) {
      return -1;
    }
    int d = dep[u] - k;
    while (dep[top[u]] > d) {
      u = par[top[u]];
    }
    return order[tin[u] - dep[u] + d];
  }

  [[nodiscard]] bool isAncestor(int u, int v) const {
    return tin[u] <= tin[v] && tin[v] < tout[u];
  }

  [[nodiscard]] int rootedParent(int u, int v) const {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    std::swap(u, v);
    if (u == v) {
      return -1;
    }
    if (!isAncestor(u, v)) {
      return par[u];
    }
    auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
      return tin[x] < tin[y];
    });
    return *std::prev(it);
  }

  [[nodiscard]] int rootedSize(int u, int v) const {
    assert(0 <= u && u < n);
    assert(0 <= v && v < n);
    if (u == v) {
      return n;
    }
    if (!isAncestor(v, u)) {
      return siz[v];
    }
    return n - siz[rootedParent(u, v)];
  }

  [[nodiscard]] int rootedLca(int a, int b, int c) const {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    assert(0 <= c && c < n);
    return getLca(a, b) ^ getLca(b, c) ^ getLca(c, a);
  }
};