text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Adjacency List representation of a graph using linked list,
//   implemented with fixed size arrays if reserveEdges is called beforehand
// Vertices are 0-indexed
// Constructor Arguments:
//   V: the number of vertices in the graph
// Functions:
//   reserveDiEdges(maxEdges): reserves space for maxEdges directed edges
//     (bidirectional edges take up twice as much space)
//   addDiEdge(from, to): adds a directed edge from the vertex from,
//     to the vertex to
//   addBiEdge(v, w): adds a bidirectional edge between vertices v and w
//   operator [v]: returns a struct with the begin() and end() defined to
//     iterate over the vertices adjacent to vertex v
//   size(): returns the number of vertices in the graph
// In practice, addBiEdge, addDiEdge have a small constant, operator []
//   has a moderate constant
// Graph construction is faster than static graphs and adjacency lists
// Graph traveral is slower than static graphs and adjacency lists
// Uses less memory than static graphs and adjacency lists
// Time Complexity:
//   constructor: O(V)
//   addDiEdge: O(1) amortized
//   operator [], size: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://judge.yosupo.jp/problem/lca
struct LinkedListGraph {
  vector<int> HEAD, TO, NXT; LinkedListGraph(int V) : HEAD(V, -1) {}
  void reserveDiEdges(int maxEdges) {
    TO.reserve(maxEdges); NXT.reserve(maxEdges);
  }
  void addDiEdge(int from, int to) {
    NXT.push_back(HEAD[from]); HEAD[from] = int(TO.size()); TO.push_back(to);
  }
  void addBiEdge(int v, int w) { addDiEdge(v, w); addDiEdge(w, v); }
  struct Iterator {
    const LinkedListGraph &G; int i;
    Iterator(const LinkedListGraph &G, int i) : G(G), i(i) {}
    Iterator &operator ++ () { i = G.NXT[i]; return *this; }
    int operator * () const { return G.TO[i]; }
    bool operator != (const Iterator &it) const { return i != it.i; }
  };
  struct Adj {
    const LinkedListGraph &G; int v;
    Adj(const LinkedListGraph &G, int v) : G(G), v(v) {}
    const Iterator begin() const { return Iterator(G, G.HEAD[v]); }
    const Iterator end() const { return Iterator(G, -1); }
  };
  const Adj operator [] (int v) const { return Adj(*this, v); }
  int size() const { return HEAD.size(); }
};

// Adjacency List representation of a weighted graph using linked list,
//   implemented with fixed size arrays if reserveEdges is called beforehand
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges in the weighted graph
// Constructor Arguments:
//   V: the number of vertices in the weighted graph
// Functions:
//   reserveDiEdges(maxEdges): reserves space for maxEdges directed edges
//     (bidirectional edges take up twice as much space)
//   addDiEdge(from, to, weight): adds a directed edge from the vertex from,
//     to the vertex to, with a weight of weight
//   addBiEdge(v, w, weight): adds a bidirectional edge between vertices v
//     and w, with a weight of weight
//   operator [v]: returns a struct with the begin() and end() defined to
//     iterate over the edges incident to vertex v
//   size(): returns the number of vertices in the graph
// In practice, addBiEdge, addDiEdge have a small constant, operator []
//   has a moderate constant
// Graph construction is faster than static graphs and adjacency lists
// Graph traveral is slower than static graphs and adjacency lists
// Uses less memory than static graphs and adjacency lists
// Time Complexity:
//   constructor: O(V)
//   addBiEdge, addDiEdge: O(1) amortized
//   operator [], size: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://dmoj.ca/problem/rte16s3
template <class T> struct LinkedListWeightedGraph {
  vector<int> HEAD, TO, NXT; vector<T> WEIGHT;
  LinkedListWeightedGraph(int V) : HEAD(V, -1) {}
  void reserveDiEdges(int maxEdges) {
    TO.reserve(maxEdges); NXT.reserve(maxEdges); WEIGHT.reserve(maxEdges);
  }
  void addDiEdge(int from, int to, T weight) {
    NXT.push_back(HEAD[from]); HEAD[from] = int(TO.size());
    TO.push_back(to); WEIGHT.push_back(weight);
  }
  void addBiEdge(int v, int w, T weight) {
    addDiEdge(v, w, weight); addDiEdge(w, v, weight);
  }
  struct Iterator {
    const LinkedListWeightedGraph &G; int i;
    Iterator(const LinkedListWeightedGraph &G, int i) : G(G), i(i) {}
    Iterator &operator ++ () { i = G.NXT[i]; return *this; }
    pair<int, T> operator * () const {
      return make_pair(G.TO[i], G.WEIGHT[i]);
    }
    bool operator != (const Iterator &it) const { return i != it.i; }
  };
  struct Adj {
    const LinkedListWeightedGraph &G; int v;
    Adj(const LinkedListWeightedGraph &G, int v) : G(G), v(v) {}
    const Iterator begin() const { return Iterator(G, G.HEAD[v]); }
    const Iterator end() const { return Iterator(G, -1); }
  };
  const Adj operator [] (int v) const { return Adj(*this, v); }
  int size() const { return HEAD.size(); }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Static Graph implemented with fixed size arrays
//   if reserveEdges is called beforehand
// build must be called before the graph can be used, and edges cannot be
//   added afterwards
// Vertices are 0-indexed
// Constructor Arguments:
//   V: the number of vertices in the graph
// Functions:
//   reserveDiEdges(maxEdges): reserves space for maxEdges directed edges
//     (bidirectional edges take up twice as much space)
//   addDiEdge(from, to): adds a directed edge from the vertex from,
//     to the vertex to
//   addBiEdge(v, w): adds a bidirectional edge between vertices v and w
//   operator [v]: returns a struct with the begin() and end() defined to
//     iterate over the vertices adjacent to vertex v
//   size(): returns the number of vertices in the graph
//   build(): builds a graph using the edges that have been added
// In practice, addBiEdge and addDiEdge have a small constant, build has a
//   moderate constant, and operator [] has a very small constant
// Graph construction is faster than adjacency lists, but slower than
//   linked lists
// Graph traveral is faster than adjacency lists and linked lists
// Uses less memory than adjacency lists, but more memory than linked lists
// Time Complexity:
//   constructor: O(V)
//   addDiEdge: O(1) amortized
//   build: O(V + E)
//   operator [], size: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://judge.yosupo.jp/problem/lca
struct StaticGraph {
  vector<int> ST, TO, A, B; StaticGraph(int V) : ST(V + 1, 0) {}
  void reserveDiEdges(int maxEdges) {
    TO.reserve(maxEdges); A.reserve(maxEdges); B.reserve(maxEdges);
  }
  void addDiEdge(int from, int to) {
    ST[from]++; A.push_back(from); B.push_back(to);
  }
  void addBiEdge(int v, int w) { addDiEdge(v, w); addDiEdge(w, v); }
  void build() {
    partial_sum(ST.begin(), ST.end(), ST.begin()); TO = B;
    for (int e = 0; e < int(A.size()); e++) TO[--ST[A[e]]] = B[e];
  }
  struct Iterator {
    const StaticGraph &G; int i;
    Iterator(const StaticGraph &G, int i) : G(G), i(i) {}
    Iterator &operator ++ () { i++; return *this; }
    int operator * () const { return G.TO[i]; }
    bool operator != (const Iterator &it) const { return i != it.i; }
  };
  struct Adj {
    const StaticGraph &G; int v;
    Adj(const StaticGraph &G, int v) : G(G), v(v) {}
    const Iterator begin() const { return Iterator(G, G.ST[v]); }
    const Iterator end() const { return Iterator(G, G.ST[v + 1]); }
  };
  const Adj operator [] (int v) const { return Adj(*this, v); }
  int size() const { return int(ST.size()) - 1; }
};

// Static Weighted Graph implemented with fixed size arrays
//   if reserveEdges is called beforehand
// build must be called before the graph can be used, and edges cannot be
//   added afterwards
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges in the weighted graph
// Constructor Arguments:
//   V: the number of vertices in the weighted graph
// Functions:
//   reserveDiEdges(maxEdges): reserves space for maxEdges directed edges
//     (bidirectional edges take up twice as much space)
//   addDiEdge(from, to, weight): adds a directed edge from the vertex from,
//     to the vertex to, with a weight of weight
//   addBiEdge(v, w, weight): adds a bidirectional edge between vertices v
//     and w, with a weight of weight
//   operator [v]: returns a struct with the begin() and end() defined to
//     iterate over the edges incident to vertex v
//   size(): returns the number of vertices in the graph
//   build(): builds a graph using the edges that have been added
// In practice, addBiEdge and addDiEdge have a small constant, build has a
//   moderate constant, and operator [] has a very small constant
// Graph construction is faster than adjacency lists, but slower than
//   linked lists
// Graph traveral is faster than adjacency lists and linked lists
// Uses less memory than adjacency lists, but more memory than linked lists
// Time Complexity:
//   constructor: O(V)
//   addBiEdge, addDiEdge: O(1) amortized
//   build: O(V + E)
//   operator [], size: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://dmoj.ca/problem/rte16s3
template <class T> struct StaticWeightedGraph {
  vector<int> ST, TO, A, B; vector<T> C, WEIGHT;
  StaticWeightedGraph(int V) : ST(V + 1, 0) {}
  void reserveDiEdges(int maxEdges) {
    TO.reserve(maxEdges); A.reserve(maxEdges); B.reserve(maxEdges);
  }
  void addDiEdge(int from, int to, T weight) {
    ST[from]++; A.push_back(from); B.push_back(to); C.push_back(weight);
  }
  void addBiEdge(int v, int w, T weight) {
    addDiEdge(v, w, weight); addDiEdge(w, v, weight);
  }
  void build() {
    partial_sum(ST.begin(), ST.end(), ST.begin()); TO = B; WEIGHT = C;
    for (int e = 0; e < int(A.size()); e++) {
      TO[--ST[A[e]]] = B[e]; WEIGHT[ST[A[e]]] = C[e];
    }
  }
  struct Iterator {
    const StaticWeightedGraph &G; int i;
    Iterator(const StaticWeightedGraph &G, int i) : G(G), i(i) {}
    Iterator &operator ++ () { i++; return *this; }
    pair<int, T> operator * () const {
      return make_pair(G.TO[i], G.WEIGHT[i]);
    }
    bool operator != (const Iterator &it) const { return i != it.i; }
  };
  struct Adj {
    const StaticWeightedGraph &G; int v;
    Adj(const StaticWeightedGraph &G, int v) : G(G), v(v) {}
    const Iterator begin() const { return Iterator(G, G.ST[v]); }
    const Iterator end() const { return Iterator(G, G.ST[v + 1]); }
  };
  const Adj operator [] (int v) const { return Adj(*this, v); }
  int size() const { return int(ST.size()) - 1; }
};

repo_name: wesley-a-leung/Resources

mime_type: text/x-c++


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Adjacency List representation of a graph
// Vertices are 0-indexed
// Constructor Arguments:
//   V: the number of vertices in the graph
// Functions:
//   addDiEdge(from, to): adds a directed edge from the vertex from,
//     to the vertex to
//   addBiEdge(v, w): adds a bidirectional edge between vertices v and w
//   operator [v]: returns a reference to a list of vertices adjacent to v
//   size(): returns the number of vertices in the graph
// In practice, addBiEdge, addDiEdge have a moderate constant, operator []
//   has a small constant
// Graph construction is slower than static graphs and linked lists
// Graph traveral is faster than static graphs, but slower than linked lists
// Uses more memory than static graphs and linked lists
// Time Complexity:
//   constructor: O(V)
//   addBiEdge, addDiEdge: O(1) amortized
//   operator [], size: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://judge.yosupo.jp/problem/lca
struct AdjacencyListGraph : public vector<vector<int>> {
  AdjacencyListGraph(int V) : vector<vector<int>>(V) {}
  void addDiEdge(int from, int to) { at(from).push_back(to); }
  void addBiEdge(int v, int w) { addDiEdge(v, w); addDiEdge(w, v); }
};

// Adjacency List representation of a weighted graph
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges in the weighted graph
// Constructor Arguments:
//   V: the number of vertices in the weighted graph
// Functions:
//   addDiEdge(from, to, weight): adds a directed edge from the vertex from,
//     to the vertex to, with a weight of weight
//   addBiEdge(v, w, weight): adds a bidirectional edge between vertices v
//     and w, with a weight of weight
//   operator [v]: returns a reference to a list of edges incident to v
//   size(): returns the number of vertices in the graph
// In practice, addBiEdge, addDiEdge have a moderate constant, operator []
//   has a small constant
// Graph construction is slower than static graphs and linked lists
// Graph traveral is faster than static graphs, but slower than linked lists
// Uses more memory than static graphs and linked lists
// Time Complexity:
//   constructor: O(V)
//   addBiEdge, addDiEdge: O(1) amortized
//   operator [], size: O(1)
// Memory Complexity: O(V + E)
// Tested:
//   https://dmoj.ca/problem/rte16s3
template <class T>
struct AdjacencyListWeightedGraph : public vector<vector<pair<int, T>>> {
  AdjacencyListWeightedGraph(int V) : vector<vector<pair<int, T>>>(V) {}
  void addDiEdge(int from, int to, T weight) {
    this->at(from).emplace_back(to, weight);
  }
  void addBiEdge(int v, int w, T weight) {
    addDiEdge(v, w, weight); addDiEdge(w, v, weight);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Runs a callback on the triangles in a simple graph
// Vertices are 0-indexed
// Template Arguments:
//   F: the type of the function f
// Function Arguments:
//   V: the number of vertices in the simple graph
//   edges: a vector of pairs in the form (v, w) representing
//     an undirected edge in the simple graph (no self loops or parallel edges)
//     between vertices v and w
//   f(a, b, c, i, j, k): the function to run a callback on for each triangle
//     where a, b, c are the vertices in the triangle, and i, j, k are the
//     indices of the edges in the triangle
// In practice, has a very small constant
// Time Complexity: O(V + E sqrt E)
// Memory Complexity: O(V + E)
// Tested:
//   Fuzz and Stress Tested
//   https://mcpt.ca/problem/lcc19c3s4
//   https://open.kattis.com/problems/gottacatchemall
//   https://judge.yosupo.jp/problem/enumerate_triangles
//   https://dmoj.ca/problem/year2019p7
template <class F>
void triangles(int V, const vector<pair<int, int>> &edges, F f) {
  vector<int> st(V + 1, 0), ind(V, 0), to(edges.size()), eInd(edges.size());
  vector<int> &d = ind; for (auto &&e : edges) { d[e.first]++; d[e.second]++; }
  auto cmp = [&] (int v, int w) { return d[v] == d[w] ? v > w : d[v] > d[w]; };
  for (auto &&e : edges) st[cmp(e.first, e.second) ? e.second : e.first]++;
  partial_sum(st.begin(), st.end(), st.begin());
  for (int i = 0, v, w; i < int(edges.size()); i++) {
    tie(v, w) = edges[i]; if (cmp(v, w)) swap(v, w);
    to[--st[v]] = w; eInd[st[v]] = i;
  }
  fill(ind.begin(), ind.end(), -1); for (int v = 0; v < V; v++) {
    for (int e1 = st[v]; e1 < st[v + 1]; e1++) ind[to[e1]] = eInd[e1];
    for (int e1 = st[v]; e1 < st[v + 1]; e1++)
      for (int w = to[e1], e2 = st[w]; e2 < st[w + 1]; e2++)
        if (ind[to[e2]] != -1)
          f(v, w, to[e2], eInd[e1], eInd[e2], ind[to[e2]]);
    for (int e1 = st[v]; e1 < st[v + 1]; e1++) ind[to[e1]] = -1;
  }
}


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Finds a directed cycle in a directed graph (including self loops and
//   parallel edges)
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic directed graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   cycle: a vector of the vertices in the directed cycle with the first
//     vertex equal to the last vertex; if there is no cycle, then it is empty
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V + E)
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://cses.fi/problemset/task/1678
//   https://judge.yosupo.jp/problem/cycle_detection
struct DirectedCycle {
  int V; vector<bool> vis, onStk; vector<int> to, cycle;
  template <class Digraph> void dfs(const Digraph &G, int v) {
    vis[v] = onStk[v] = true; for (int w : G[v]) {
      if (!vis[w]) { to[w] = v; dfs(G, w); }
      else if (onStk[w]) {
        for (int x = v; x != w; x = to[x]) cycle.push_back(x);
        cycle.push_back(w); cycle.push_back(v);
        reverse(cycle.begin(), cycle.end());
      }
      if (!cycle.empty()) return;
    }
    onStk[v] = false;
  }
  template <class Digraph> DirectedCycle(const Digraph &G)
      : V(G.size()), vis(V, false), onStk(V, false), to(V) {
    for (int v = 0; v < V && cycle.empty(); v++) if (!vis[v]) dfs(G, v);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Finds a cycle in an undirected graph (including self loops and
//   parallel edges)
// Vertices are 0-indexed
// Constructor Arguments:
//   G: a generic undirected graph structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the graph
// Fields:
//   cycle: a vector of the vertices in the cycle with the first vertex equal
//     to the last vertex; if there is no cycle, then it is empty
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V + E)
// Memory Complexity: O(V)
// Tested:
//   Stress Tested
//   https://cses.fi/problemset/task/1669
struct Cycle {
  int V; vector<bool> vis; vector<int> to, cycle;
  template <class Graph> void dfs(const Graph &G, int v, int prev) {
    vis[v] = true; for (int w : G[v]) {
      if (!vis[w]) dfs(G, w, to[w] = v);
      else if (w != prev) {
        for (int x = v; x != w; x = to[x]) cycle.push_back(x);
        cycle.push_back(w); cycle.push_back(v);
      }
      if (!cycle.empty()) return;
    }
  }
  template <class Graph>
  Cycle(const Graph &G) : V(G.size()), vis(V, false), to(V) {
    for (int v = 0; v < V; v++) {
      for (int w : G[v]) {
        if (v == w) { cycle.push_back(v); cycle.push_back(v); return; }
        if (vis[w]) {
          cycle.push_back(v); cycle.push_back(w); cycle.push_back(v); return;
        }
      }
      for (int w : G[v]) vis[w] = false;
    }
    fill(vis.begin(), vis.end(), false);
    for (int v = 0; v < V && cycle.empty(); v++) if (!vis[v]) dfs(G, v, -1);
  }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Finds an Eulerian walk (or a circuit) in a graph which can be
//   either undirected or directed
// A undirected walk exists iff every exactly zero of two vertices has an odd
//   degree and all nonzero degree vertices are in a single connected component
// A undirected circuit exists iff every vertex has an even degree
//   and all nonzero degree vertices are in a single connected component
// A directed walk exists iff at most one vertex has outDeg - inDeg = 1 and at
//   most one vertex has inDeg - outDeg = 1, with all other vertices having
//   inDeg = outDeg and all vertices all nonzero degree vertices are in a
//   single connected component of the underlying undirected graph
// A directed circuit exists iff all vertices have inDeg = outDeg and all
//   nonzero degree vertices are in a single strongly connected component
// Vertices are 0-indexed
// Function Arguments:
//   V: number of vertices in the graph
//   edges: a vector of pairs in the form (v, w) representing
//     an edge in the simple graph between vertices v and w, each edge should
//     be specified exactly once regardless of whether the graph is
//     directed or undirected
//   directed: a boolean indicating whether the graph is directed or not
//   circuit: a boolean indicating whether the Eulerian walk is required to be
//     a circuit (first vertex equal to last)
//   s: the starting vertex of the Eulerian walk, or -1 if any vertex can be
//     the starting vertex
// Return Value: the vertices in the Eulerian walk with the first vertex
//   either equal to s if s is non negative, or any arbitrary vertex if
//   s is -1, and the last vertex equal to the first vertex if circuit is true,
//   and any vertex otherwise
// In practice, has a moderate constant
// Time Complexity: O(V + E)
// Memory Complexity: O(V + E)
// Tested:
//   Stress Tested
//   https://open.kattis.com/problems/eulerianpath
//   https://cses.fi/problemset/task/1691/
//   https://cses.fi/problemset/task/1693/
vector<int> eulerianWalk(int V, const vector<pair<int, int>> &edges,
                         bool directed, bool circuit, int s = -1) {
  if (V == 0) return vector<int>();
  else if (edges.empty()) return vector<int>{0};
  vector<int> st(V + 1, 0), d(V, 0), walk; walk.reserve(edges.size() + 1);
  vector<int> to(edges.size() * (directed ? 1 : 2)), eInd(to.size());
  for (auto &&e : edges) {
    st[e.first]++; d[e.second]++;
    if (!directed) { st[e.second]++; d[e.first]++; }
  }
  if (s == -1) {
    s = edges[0].first; if (circuit) {}
    else if (directed) { for (int v = 0; v < V; v++) if (st[v] > d[v]) s = v; }
    else { for (int v = 0; v < V; v++) if (d[v] % 2 == 1) s = v; }
  }
  partial_sum(st.begin(), st.end(), st.begin()); fill(d.begin(), d.end(), 0);
  for (int i = 0, v, w; i < int(edges.size()); i++) {
    tie(v, w) = edges[i]; to[--st[v]] = w; eInd[st[v]] = i;
    if (!directed) { to[--st[w]] = v; eInd[st[w]] = i; }
  }
  vector<int> cur = st, stk(edges.size() + 1);
  vector<bool> vis(edges.size(), false);
  int top = 0; d[stk[top++] = s]++; while (top > 0) {
    int v = stk[top - 1];
    if (cur[v] == st[v + 1]) { walk.push_back(v); --top; continue; }
    int w = to[cur[v]], e = eInd[cur[v]++];
    if (!vis[e]) { d[v]--; d[stk[top++] = w]++; vis[e] = true; }
  }
  if ((circuit && walk[0] != walk.back())
      || walk.size() != edges.size() + 1) return vector<int>();
  for (int di : d) if (di < 0) return vector<int>();
  reverse(walk.begin(), walk.end()); return walk;
}


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Counts the number of 4-cycles in a simple graph
// Vertices are 0-indexed
// Function Arguments:
//   V: the number of vertices in the simple graph
//   edges: a vector of pairs in the form (v, w) representing
//     an undirected edge in the simple graph (no self loops or parallel edges)
//     between vertices v and w
// In practice, has a very small constant
// Time Complexity: O(V + E sqrt E)
// Memory Complexity: O(V + E)
// Tested:
//   Fuzz and Stress Tested
long long fourCycles(int V, const vector<pair<int, int>> &edges) {
  vector<int> st1(V + 1, 0), st2(V + 1, 0), d(V, 0);
  vector<int> to1(edges.size()), to2(edges.size());
  for (auto &&e : edges) { d[e.first]++; d[e.second]++; }
  auto cmp = [&] (int v, int w) { return d[v] == d[w] ? v > w : d[v] > d[w]; };
  for (auto &&e : edges) {
    int v, w; tie(v, w) = e; if (cmp(v, w)) swap(v, w);
    st1[v]++; st2[w]++;
  }
  partial_sum(st1.begin(), st1.end(), st1.begin());
  partial_sum(st2.begin(), st2.end(), st2.begin()); for (auto &&e : edges) {
    int v, w; tie(v, w) = e; if (cmp(v, w)) swap(v, w);
    to1[--st1[v]] = w; to2[--st2[w]] = v;
  }
#define loop(h) for (int e1 = st##h[v]; e1 < st##h[v + 1]; e1++) \
    for (int w = to##h[e1], e2 = st1[w]; e2 < st1[w + 1]; e2++)
  long long ret = 0; vector<long long> cnt(V, 0); for (int v = 0; v < V; v++) {
    loop(1) if (cmp(to1[e2], v)) ret += cnt[to1[e2]]++;
    loop(2) if (cmp(to1[e2], v)) ret += cnt[to1[e2]]++;
    loop(1) cnt[to1[e2]] = 0;
    loop(2) cnt[to1[e2]] = 0;
  }
#undef loop
  return ret;
}


text:
#pragma once
#include <bits/stdc++.h>
#include "HeavyLightDecomposition.h"
using namespace std;

// Supports path (and subtree) updates and queries on a forest
// Vertices and indices are 0-indexed
// Template Arguments:
//   R: struct supporting range updates and queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static merge(l, r): merges the datas l and r, must be associative
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(l, r, val, rev): updates the range [l, r] with the value
//         val, with rev indicating if the update range should be updated
//         right to left
//       query(l, r, rev): queries the range [l, r] with rev indicating
//         if the result needs to be reversed
//     Sample Struct: supporting range assignment and maximum subarray sum
//       struct R {
//         using Data = MaxSubarraySumCombine<int>::Data;
//         using Lazy = MaxSubarraySumCombine<int>::Lazy;
//         static Data qdef() { return MaxSubarraySumCombine<int>::qdef(); }
//         static Data merge(const Data &l, const Data &r) {
//           return MaxSubarraySumCombine<int>::merge(l, r);
//         }
//         SegmentTreeLazyBottomUp<MaxSubarraySumCombine<int>> ST;
//         R(vector<Data> A) : ST(move(A)) {}
//         void update(int l, int r, const Lazy &val, bool) {
//           ST.update(l, r, val);
//         }
//         Data query(int l, int r, bool rev) {
//           Data ret = ST.query(l, r);
//           if (rev) swap(ret.pre, ret.suf);
//           return ret;
//         }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type R::Data with the initial value of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Functions:
//   updatePath(v, w, val): updates the path from v to w with the value val
//   updateVertex(v, val): updates the vertex v with the value val
//   updateSubtree(v, val): updates the subtree of vertex v with the value val
//   queryPath(v, w): queries the path from v to w
//   queryVertex(v): queries the vertex v
//   querySubtree(v): queries the subtree of vertex v
// In practice, constructor has a moderate constant,
//   update and query functions have a small constant
// Time Complexity:
//   constructor: O(V) + time complexity of R's constructor
//   updatePath, queryPath: O(log V) * time complexity of R's update/query
//   updateVertex, updateSubtree, queryVertex, querySubtree:
//     time complexity of R's update/query
// Memory Complexity: O(V) + memory complexity of R
// Tested:
//   https://www.spoj.com/problems/GSS7/
//   https://judge.yosupo.jp/problem/vertex_set_path_composite
template <class R, const bool VALUES_ON_EDGES>
struct PathQueries : public HLD {
  using Data = typename R::Data; using Lazy = typename R::Lazy; R ops;
  void updatePath(int v, int w, const Lazy &val) {
    while (head[v] != head[w]) {
      if (dep[head[v]] < dep[head[w]]) {
        ops.update(pre[head[w]], pre[w], val, false); w = par[head[w]];
      } else { ops.update(pre[head[v]], pre[v], val, true); v = par[head[v]]; }
    }
    if (v != w) {
      if (dep[v] < dep[w])
        ops.update(pre[v] + VALUES_ON_EDGES, pre[w], val, false);
      else ops.update(pre[w] + VALUES_ON_EDGES, pre[v], val, true);
    } else if (!VALUES_ON_EDGES) {
      int i = pre[dep[v] < dep[w] ? v : w]; ops.update(i, i, val, false);
    }
  }
  void updateVertex(int v, const Lazy &val) {
    ops.update(pre[v], pre[v], val, false);
  }
  void updateSubtree(int v, const Lazy &val) {
    int l = pre[v] + VALUES_ON_EDGES, r = post[v];
    if (l <= r) ops.update(l, r, val, false);
  }
  Data queryPath(int v, int w) {
    Data qu = R::qdef(), qd = R::qdef(); while (head[v] != head[w]) {
      if (dep[head[v]] < dep[head[w]]) {
        qd = R::merge(ops.query(pre[head[w]], pre[w], false), qd);
        w = par[head[w]];
      } else {
        qu = R::merge(qu, ops.query(pre[head[v]], pre[v], true));
        v = par[head[v]];
      }
    }
    if (v != w) {
      if (dep[v] < dep[w])
        qu = R::merge(qu, ops.query(pre[v] + VALUES_ON_EDGES, pre[w], false));
      else
        qd = R::merge(ops.query(pre[w] + VALUES_ON_EDGES, pre[v], true), qd);
    } else if (!VALUES_ON_EDGES) {
      int i = pre[dep[v] < dep[w] ? v : w];
      qu = R::merge(qu, ops.query(i, i, false));
    }
    return R::merge(qu, qd);
  }
  Data queryVertex(int v) { return ops.query(pre[v], pre[v], false); }
  Data querySubtree(int v) {
    int l = pre[v] + VALUES_ON_EDGES, r = post[v];
    return l <= r ? ops.query(l, r, false) : R::qdef();
  }
  vector<Data> reorder(const vector<Data> &A) {
    vector<Data> ret; ret.reserve(A.capacity());
    for (int i = 0; i < V; i++) ret.push_back(A[vert[i]]);
    return ret;
  }
  template <class Forest>
  PathQueries(const Forest &G, const vector<Data> &A,
              const vector<int> &roots = vector<int>())
      : HLD(G, roots), ops(reorder(A)) {}
  template <class Forest>
  PathQueries(const Forest &G, const vector<Data> &A, int rt)
      : PathQueries(G, A, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "LowestCommonAncestor.h"
using namespace std;

// Supports vertex updates and path queries for invertible operations on
//   a forest
// Vertices and indices are 0-indexed
// Template Arguments:
//   R: struct supporting point updates and range queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative and commutative
//       static invData(v): returns the inverse of v of type Data
//       static invLazy(v): returns the inverse of v of type Lazy
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(i, val): updates the index i with the value val
//       query(l, r): queries the range [l, r]
//     Sample Struct: supporting point increments and range sum queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         static Data invData(const Data &v) { return -v; }
//         static Lazy invLazy(const Lazy &v) { return -v; }
//         FenwickTree1D<Data> FT;
//         R(vector<Data> A) : FT(move(A)) {}
//         void update(int i, const Lazy &val) { FT.update(i, val); }
//         Data query(int l, int r) { return FT.query(l, r); }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type R::Data with the initial value of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Functions:
//   connected(v, w): returns true if and only if v and w are connected
//   updateVertex(v, val): updates the vertex v with the value val
//   queryPathFromRoot(v): queries the path betwen vertex v and the root of
//     its connected component
//   queryPath(v, w): queries the path between vertices v and w
// In practice, constructor has a moderate constant,
//   update and query functions have a very small constant plus
//   the constants of R's update and query functions
// Time Complexity:
//   constructor: O(V) + time complexity of R's constructor
//   connected: O(1)
//   updateVertex, queryPathFromRoot, queryPath:
//     time complexity of update/query
// Memory Complexity: O(V) + memory complexity of R
// Tested:
//   https://judge.yosupo.jp/problem/vertex_add_path_sum
//   http://www.usaco.org/index.php?page=viewproblem2&cpid=921
template <class R, const bool VALUES_ON_EDGES>
struct InvertibleVertexUpdatesPathQueries {
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  LCA<> lca; int V, ind; vector<int> par, pre, post, vert; R ops;
  bool connected(int v, int w) { return lca.connected(v, w); }
  void updateVertex(int v, const Lazy &val) {
    ops.update(pre[v], val); if (post[v] + 1 <= post[lca.root[v]])
      ops.update(post[v] + 1, R::invLazy(val));
  }
  Data queryPathFromRoot(int v) {
    int l = pre[lca.root[v]] + int(VALUES_ON_EDGES), r = pre[v];
    return l <= r ? ops.query(pre[lca.root[v]], pre[v]) : R::qdef();
  }
  Data queryPath(int v, int w) {
    Data ret = R::merge(queryPathFromRoot(v), queryPathFromRoot(w));
    int u = lca.lca(v, w); Data inv = queryPathFromRoot(u);
    if (VALUES_ON_EDGES) inv = R::merge(inv, inv);
    else if (par[u] != -1) inv = R::merge(inv, queryPathFromRoot(par[u]));
    return R::merge(ret, R::invData(inv));
  }
  template <class Forest> void dfs(const Forest &G, int v, int prev) {
    par[v] = prev; vert[pre[v] = ++ind] = v;
    for (int w : G[v]) if (w != prev) dfs(G, w, v);
    post[v] = ind;
  }
  template <class Forest>
  vector<Data> reorder(const Forest &G, const vector<Data> &A,
                       const vector<int> &roots) {
    if (roots.empty()) {
      for (int v = 0; v < V; v++) if (par[v] == -1) dfs(G, v, -1);
    } else for (int v : roots) dfs(G, v, -1);
    vector<Data> ret; ret.reserve(A.capacity());
    for (int i = 0; i < V; i++) ret.push_back(A[vert[i]]);
    for (int v = 0; v < V; v++) if (post[v] + 1 <= post[lca.root[v]])
      ret[post[v] + 1] = R::merge(ret[post[v] + 1], R::invData(A[v]));
    return ret;
  }
  template <class Forest> InvertibleVertexUpdatesPathQueries(
      const Forest &G, const vector<Data> &A,
      const vector<int> &roots = vector<int>())
      : lca(G, roots), V(G.size()), ind(-1), par(V, -1),
        pre(V), post(V), vert(V), ops(reorder(G, A, roots)) {}
  template <class Forest> InvertibleVertexUpdatesPathQueries(
      const Forest &G, const vector<Data> &A, int rt)
      : InvertibleVertexUpdatesPathQueries(G, A, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/FischerHeunStructure.h"
using namespace std;

// Supports queries for the lowest common ancestor of 2 vertices in a forest
//   and the distance between 2 vertices by reduing the problem to a
//   range minimum query using the Fischer Heun Structure
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges in the forest
// Constructor Arguments:
//   G: a generic forest data structure (weighted or unweighted)
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints for an unweighted forest, or a list of
//         pair<int, T> for a weighted forest with weights of type T)
//       size() const: returns the number of vertices in the forest
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Fields:
//   root: vector of roots for the forest each vertex is in
//   pre: vector of the pre order traversal indices for each vertex
//   dep: vector of depths to each vertex from the root of
//     its connected component
// Functions:
//   lca(v, w): returns the lowest common ancestor of vertices v and w assuming
//     v and w are connected
//   lca(r, v, w): returns the lowest common ancestor of vertices v and w if
//     their component is rooted a r, assuming r, v, and w are connected
//   getDirectChild(anc, des): returns the direct child of anc that is on the
//     path from anc to des, where anc is an ancestor of des
//   connected(v, w): returns true if and only if v and w are connected
//   dist(v, w): returns the distance between vertices v and w assuming
//     v and w are connected
// In practice, lca and dist have a moderate constant, constructor is
//   dependent on the forest data structure
// Time Complexity:
//   constructor: O(V)
//   lca, getDirectChild, connected, dist: O(1)
// Memory Complexity: O(V)
// Tested:
//   https://judge.yosupo.jp/problem/lca
//   https://www.spoj.com/problems/LCASQ
//   https://dmoj.ca/problem/rte16s3
//   https://dmoj.ca/problem/wac1p6
//   https://www.acmicpc.net/problem/15480
template <class T = int> struct LCA {
  int V, ind; vector<int> root, pre, top, bot; vector<T> dep;
  FischerHeunStructure<int, greater_equal<int>> FHS;
  int getTo(int e) { return e; }
  T getWeight(int) { return 1; }
  int getTo(const pair<int, T> &e) { return e.first; }
  T getWeight(const pair<int, T> &e) { return e.second; }
  template <class Forest> void dfs(const Forest &G, int v) {
    pre[v] = ind; for (auto &&e : G[v]) {
      int w = getTo(e); if (pre[w] == -1) {
        dep[bot[ind] = w] = dep[top[ind] = v] + getWeight(e); ind++;
        root[w] = root[v]; dfs(G, w);
      }
    }
  }
  template <class Forest>
  vector<int> init(const Forest &G, const vector<int> &roots) {
    if (roots.empty()) {
      for (int v = 0; v < V; v++) if (pre[v] == -1) dfs(G, root[v] = v);
    } else for (int v : roots) dfs(G, root[v] = v);
    vector<int> tmp(V); for (int i = 0; i < V; i++) tmp[i] = pre[top[i]];
    return tmp;
  }
  template <class Forest>
  LCA(const Forest &G, const vector<int> &roots = vector<int>())
      : V(G.size()), ind(0), root(V, -1), pre(V, -1), top(V), bot(V),
        dep(V, T()), FHS(init(G, roots)) {}
  template <class Forest> LCA(const Forest &G, int rt)
      : LCA(G, vector<int>{rt}) {}
  int lca(int v, int w) {
    if (v == w) return v;
    if (pre[v] > pre[w]) swap(v, w);
    return top[FHS.queryInd(pre[v], pre[w] - 1)];
  }
  int lca(int r, int v, int w) {
    int a = lca(r, v), b = lca(r, w), c = lca(v, w);
    int d = dep[a] > dep[b] ? a : b; return dep[c] > dep[d] ? c : d;
  }
  int getDirectChild(int anc, int des) {
    return bot[FHS.queryInd(pre[anc], pre[des] - 1)];
  }
  bool connected(int v, int w) { return root[v] == root[w]; }
  T dist(int v, int w) { return dep[v] + dep[w] - T(2) * dep[lca(v, w)]; }
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Supports subtree updates and queries on a forest
// Vertices and indices are 0-indexed
// Template Arguments:
//   R: struct supporting range updates and queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(l, r, val): updates the range [l, r] with the value val
//       query(l, r): queries the range [l, r]
//     Sample Struct: supporting range sum updates and queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         FenwickTreeRange1D<Data> FT;
//         R(vector<Data> A) : FT(move(A)) {}
//         void update(int l, int r, const Lazy &val) { FT.update(l, r, val); }
//         Data query(int l, int r) { return FT.query(l, r); }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type R::Data with the initial value of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Fields:
//   pre: vector of the pre order traversal indices for each vertex
//   post: vector of the post order traversal indices (the last pre order index
//     in its subtree) for each vertex
//   vert: vector of vertex for each pre order index
// Functions:
//   updateVertex(v, val): updates the vertex v with the value val
//   updateSubtree(v, val): updates the subtree of vertex v with the value val
//   queryVertex(v): queries the vertex v
//   querySubtree(v): queries the subtree of vertex v
// In practice, constructor has a moderate constant,
//   update and query functions have a very small constant plus
//   the constants of R's update and query functions
// Time Complexity:
//   constructor: O(V) + time complexity of R's constructor
//   updateVertex, updateSubtree, queryVertex, querySubtree:
//     time complexity of update/query
// Memory Complexity: O(V) + memory complexity of R
// Tested:
//   https://judge.yosupo.jp/problem/vertex_add_subtree_sum
//   https://codeforces.com/contest/620/problem/E
template <class R, const bool VALUES_ON_EDGES> struct SubtreeQueries {
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  int V, ind; vector<int> pre, post, vert; R ops;
  void updateVertex(int v, const Lazy &val) {
    ops.update(pre[v], pre[v], val);
  }
  void updateSubtree(int v, const Lazy &val) {
    int l = pre[v] + VALUES_ON_EDGES, r = post[v];
    if (l <= r) ops.update(l, r, val);
  }
  Data queryVertex(int v) { return ops.query(pre[v], pre[v]); }
  Data querySubtree(int v) {
    int l = pre[v] + VALUES_ON_EDGES, r = post[v];
    return l <= r ? ops.query(l, r) : R::qdef();
  }
  template <class Forest> void dfs(const Forest &G, int v, int prev) {
    vert[pre[v] = ++ind] = v; for (int w : G[v]) if (w != prev) dfs(G, w, v);
    post[v] = ind;
  }
  template <class Forest>
  vector<Data> reorder(const Forest &G, const vector<Data> &A,
                       const vector<int> &roots) {
    if (roots.empty()) {
      for (int v = 0; v < V; v++) if (pre[v] == -1) dfs(G, v, -1);
    } else for (int v : roots) dfs(G, v, -1);
    vector<Data> ret; ret.reserve(A.capacity());
    for (int i = 0; i < V; i++) ret.push_back(A[vert[i]]);
    return ret;
  }
  template <class Forest>
  SubtreeQueries(const Forest &G, const vector<Data> &A,
                 const vector<int> &roots = vector<int>())
      : V(G.size()), ind(-1), pre(V, -1), post(V), vert(V),
        ops(reorder(G, A, roots)) {}
  template <class Forest>
  SubtreeQueries(const Forest &G, const vector<Data> &A, int rt)
      : SubtreeQueries(G, A, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "LowestCommonAncestor.h"
using namespace std;

// Supports path updates and vertex queries for invertible operations on
//   a forest
// Vertices and indices are 0-indexed
// Template Arguments:
//   R: struct supporting range updates and point queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative and commutative
//       static mergeLazy(l, r): merges the lazy values l and r
//       static invData(v): returns the inverse of v of type Data
//       static invLazy(v): returns the inverse of v of type Lazy
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(l, r, val): updates the range [l, r] with the value val
//       query(i): queries the index i
//     Sample Struct: supporting range increments and point queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         static Lazy mergeLazy(const Lazy &l, const Lazy &r) {
//           return l + r;
//         }
//         static Data invData(const Data &v) { return -v; }
//         static Lazy invLazy(const Lazy &v) { return -v; }
//         FenwickTreeRangePoint1D<Data> FT;
//         R(vector<Data> A) : FT(move(A)) {}
//         void update(int l, int r, const Lazy &val) { FT.update(l, r, val); }
//         Data query(int i) { return FT.get(i); }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type R::Data with the initial value of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Functions:
//   connected(v, w): returns true if and only if v and w are connected
//   updatePathFromRoot(v, val): updates the path betwen vertex v and
//     the root of its connected component with the lazy value val
//   updatePath(v, w, val): updates the path between vertices v and w with
//     the lazy value val
//   queryVertex(v): queries the vertex v
// In practice, constructor has a moderate constant,
//   update and query functions have a very small constant plus
//   the constants of R's update and query functions
// Time Complexity:
//   constructor: O(V) + time complexity of R's constructor
//   connected: O(1)
//   updatePathFromRoot, updatePath, queryVertex:
//     time complexity of update/query
// Memory Complexity: O(V) + memory complexity of R
// Tested:
//   http://www.usaco.org/index.php?page=viewproblem2&cpid=102
template <class R, const bool VALUES_ON_EDGES>
struct InvertiblePathUpdatesVertexQueries {
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  LCA<> lca; int V, ind; vector<int> par, pre, post, vert; R ops;
  bool connected(int v, int w) { return lca.connected(v, w); }
  void updatePathFromRoot(int v, const Lazy &val) {
    int l = pre[lca.root[v]] + int(VALUES_ON_EDGES), r = pre[v];
    if (l <= r) ops.update(l, r, val);
  }
  void updatePath(int v, int w, const Lazy &val) {
    updatePathFromRoot(v, val); updatePathFromRoot(w, val);
    int u = lca.lca(v, w); Lazy inv = R::invLazy(val);
    if (VALUES_ON_EDGES) inv = R::mergeLazy(inv, inv);
    updatePathFromRoot(u, inv);
    if (!VALUES_ON_EDGES && par[u] != -1) updatePathFromRoot(par[u], inv);
  }
  Data queryVertex(int v) {
    Data ret = ops.query(pre[v]); if (post[v] + 1 <= post[lca.root[v]])
      ret = R::merge(ret, R::invData(ops.query(post[v] + 1)));
    return ret;
  }
  template <class Forest> void dfs(const Forest &G, int v, int prev) {
    par[v] = prev; vert[pre[v] = ++ind] = v;
    for (int w : G[v]) if (w != prev) dfs(G, w, v);
    post[v] = ind;
  }
  template <class Forest>
  vector<Data> reorder(const Forest &G, const vector<Data> &A,
                       const vector<int> &roots) {
    if (roots.empty()) {
      for (int v = 0; v < V; v++) if (par[v] == -1) dfs(G, v, -1);
    } else for (int v : roots) dfs(G, v, -1);
    vector<Data> ret; ret.reserve(A.capacity());
    for (int i = 0; i < V; i++) ret.push_back(A[vert[i]]);
    for (int v = 0; v < V; v++) if (post[v] + 1 < V)
      ret[post[v] + 1] = R::merge(ret[post[v] + 1], R::invData(A[v]));
    return ret;
  }
  template <class Forest> InvertiblePathUpdatesVertexQueries(
      const Forest &G, const vector<Data> &A,
      const vector<int> &roots = vector<int>())
      : lca(G, roots), V(G.size()), ind(-1), par(V, -1),
        pre(V), post(V), vert(V), ops(reorder(G, A, roots)) {}
  template <class Forest> InvertiblePathUpdatesVertexQueries(
      const Forest &G, const vector<Data> &A, int rt)
      : InvertiblePathUpdatesVertexQueries(G, A, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/BitPrefixSumArray.h"
#include "LowestCommonAncestor.h"
using namespace std;

// Wavelet Matrix supporting 2D aggregation path queries for invertible
//   operations on a forest where the data can change, but not the keys
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the element of the array
//   R: struct supporting point updates and prefix queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative and commutative
//       static invData(v): returns the inverse of v of type Data
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(i, val): updates the index i with the value val
//       query(r): queries the prefix ending at index r
//     Sample Struct: supporting point increments updates and
//         prefix sum queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         static Data invData(const Data &v) { return -v; }
//         FenwickTree1D<Data> FT;
//         R(const vector<Data> &A) : FT(A) {}
//         void update(int i, const Lazy &val) { FT.update(i, val); }
//         Data query(int r) { return FT.query(r); }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
//   Cmp: the comparator to compare two elements
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type T of the values in the array
//   X: a vector of type R::Data containing the initial data of the array
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
//   cmp: an instance of the Cmp struct
// Functions:
//   update(v, val): updates the vertex v with the lazy value v
//   query(v, w, hi): returns the aggregate value of the data associated with
//     all elements with a key less than or equal to hi (using the comparator)
//     on the path from v to w
//   query(v, w, lo, hi): returns the aggregate value of the data associated
//     with all elements with a key of not less than lo and not greater than hi
//     (using the comparator) on the path from v to w
//   bsearch(v, w, f): over all keys in the array, finds the first key k such
//     that query(v, w, k) returns true
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O((V + C) log V) where C is the time complexity of
//     R's constructor
//   update: O(U log V) where U is the time complexity of R's update function
//   query, bsearch: O(Q log V) where Q is the time complexity of
//     R's query function
// Memory Complexity: O(V + (V log V) / 64 + M log V) where M is the memory
//   complexity of R
// Tested:
//   Fuzz and Stress Tested
template <class T, class R, const bool VALUES_ON_EDGES, class Cmp = less<T>>
struct WaveletMatrixTreeAggregation {
#define clt [&] (const T &a, const T &b) { return cmp(a, b); }
#define cle [&] (const T &a, const T &b) { return !cmp(b, a); }
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  int V, H, preInd, postInd; vector<int> par, pre, post, last, mid1, mid2;
  vector<T> S; LCA<> lca; vector<BitPrefixSumArray> B1, B2; vector<R> D1, D2;
  Cmp cmp;
  template <class Forest> void dfs(const Forest &G, int v, int prev) {
    par[v] = prev; last[pre[v] = preInd++] = postInd - 1;
    for (int w : G[v]) if (w != prev) dfs(G, w, v);
    post[v] = postInd++;
  }
  void build(const vector<int> &A, const vector<Data> &X,
             const vector<int> &ind, vector<int> &mid,
             vector<BitPrefixSumArray> &B, vector<R> &D) {
    vector<int> C(V), P(V); vector<Data> Y = X, Z = X; D.reserve(H);
    for (int v = 0; v < V; v++) { C[ind[v]] = A[v]; Y[ind[v]] = X[v]; }
    iota(P.begin(), P.end(), 0); for (int h = H - 1; h >= 0; h--) {
      int ph = 1 << h;
      for (int i = 0; i < V; i++) B[h].set(i, C[P[i]] <= ph - 1);
      mid[h] = stable_partition(P.begin(), P.end(), [&] (int i) {
                                  return C[i] <= ph - 1;
                                }) - P.begin();
      B[h].build(); for (int i = 0; i < V; i++) Z[i] = Y[P[i]];
      D.emplace_back(Z); for (int i = mid[h]; i < V; i++) C[P[i]] -= ph;
    }
    reverse(D.begin(), D.end());
  }
  template <class Forest>
  WaveletMatrixTreeAggregation(
      const Forest &G, const vector<T> &A, const vector<Data> &X,
      const vector<int> &roots = vector<int>(), Cmp cmp = Cmp())
      : V(A.size()), H(V == 0 ? 0 : __lg(V) + 1), preInd(0), postInd(0),
        par(V, -1), pre(V), post(V), last(V), mid1(H), mid2(H),
        S(A), lca(G, roots), B1(H, BitPrefixSumArray(V)), B2(B1), cmp(cmp) {
    sort(S.begin(), S.end(), cmp); if (roots.empty()) {
      for (int v = 0; v < V; v++) if (par[v] == -1) dfs(G, v, -1);
    } else for (int v : roots) dfs(G, v, -1);
    vector<int> C(V); for (int v = 0; v < V; v++)
      C[v] = lower_bound(S.begin(), S.end(), A[v], cmp) - S.begin();
    build(C, X, pre, mid1, B1, D1); build(C, X, post, mid2, B2, D2);
  }
  template <class Forest>
  WaveletMatrixTreeAggregation(const Forest &G, const vector<T> &A,
                               const vector<Data> &X, int rt, Cmp cmp = Cmp())
      : WaveletMatrixTreeAggregation(G, A, X, vector<int>{rt}, cmp) {}
  bool connected(int v, int w) { return lca.connected(v, w); }
  using Ranges = vector<tuple<int, int, int, int, int>>;
  Ranges getRanges(int v, int w) {
    int u = lca.lca(v, w), rt = lca.root[v]; Ranges ranges; ranges.reserve(5);
    int t = VALUES_ON_EDGES ? 1 : (par[u] != -1 ? 2 : 0);
    if (t && pre[rt] - 1 > 0)
      ranges.emplace_back(pre[rt] - 1, last[pre[rt] - 1], -1, 0, 0);
    ranges.emplace_back(pre[v], last[pre[v]], 1, 0, 0);
    ranges.emplace_back(pre[w], last[pre[w]], 1, 0, 0);
    ranges.emplace_back(pre[u], last[pre[u]], t == 1 ? -2 : -1, 0, 0);
    if (t == 2) ranges.emplace_back(pre[par[u]], last[pre[par[u]]], -1, 0, 0);
    return ranges;
  }
  void update(int v, const Lazy &val) {
    for (int a = pre[v], b = post[v], h = H - 1; h >= 0; h--) {
      if (B1[h].get(a)) a = B1[h].query(a - 1);
      else a += mid1[h] - B1[h].query(a - 1);
      if (B2[h].get(b)) b = B2[h].query(b - 1);
      else b += mid2[h] - B2[h].query(b - 1);
      D1[h].update(a, val); D2[h].update(b, val);
    }
  }
  void qryRanges(int h, Ranges &ranges) {
    for (auto &&r : ranges) {
      get<3>(r) = B1[h].query(get<0>(r)); get<4>(r) = B2[h].query(get<1>(r));
    }
  }
  Data qryAgg(int h, const Ranges &ranges) {
    Data ret = R::qdef(); for (auto &&r : ranges) {
      int a = get<3>(r) - 1, b = get<4>(r) - 1, t = get<2>(r);
      Data q = a >= 0 ? D1[h].query(a) : R::qdef();
      if (b >= 0) q = R::merge(q, R::invData(D2[h].query(b)));
      if (t <= -1) q = R::invData(q);
      if (t == -2) q = R::merge(q, q);
      ret = R::merge(ret, q);
    }
    return ret;
  }
  void left(Ranges &ranges) {
    for (auto &&r : ranges) {
      get<0>(r) = get<3>(r) - 1; get<1>(r) = get<4>(r) - 1;
    }
  }
  void right(int h, Ranges &ranges) {
    for (auto &&r : ranges) {
      get<0>(r) += mid1[h] - get<3>(r); get<1>(r) += mid2[h] - get<4>(r);
    }
  }
  template <class F> Data qry(int v, int w, const T &x, F f) {
    Ranges ranges = getRanges(v, w); Data ret = R::qdef();
    for (int cur = 0, h = H - 1; h >= 0; h--) {
      int ph = 1 << h; qryRanges(h, ranges);
      if (cur + ph - 1 >= V || f(x, S[cur + ph - 1])) left(ranges);
      else {
        ret = R::merge(ret, qryAgg(h, ranges)); cur += ph; right(h, ranges);
      }
    }
    return ret;
  }
  Data query(int v, int w, const T &hi) { return qry(v, w, hi, clt); }
  Data query(int v, int w, const T &lo, const T &hi) {
    return R::merge(qry(v, w, hi, clt), R::invData(qry(v, w, lo, cle)));
  }
  template <class F> pair<bool, T *> bsearch(int v, int w, F f) {
    Ranges ranges = getRanges(v, w);
    int cur = 0; Data agg = R::qdef(); for (int h = H - 1; h >= 0; h--) {
      qryRanges(h, ranges); Data val = qryAgg(h, ranges);
      if (f(R::merge(agg, val))) left(ranges);
      else { cur += 1 << h; agg = R::merge(agg, val); right(h, ranges); }
    }
    return make_pair(cur < V, cur < V ? &S[cur] : nullptr);
  }
#undef clt
#undef cle
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Decomposes a tree into chains, such that a path from any vertex to the root
//   will cover at most O(log V) chains
// Can be used with PathQueries for path queries
// Vertices and indices are 0-indexed
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Fields:
//   root: vector of roots for the forest each vertex is in
//   dep: vector of depths to each vertex from the root of
//     its connected component
//   par: vector of parent vertices for each vertex (or -1 if its a root)
//   size: vector of sizes of the subtree for each vertex
//   head: vector of the head of the chain of each vertex
//   pre: vector of the pre order traversal indices for each vertex
//   post: vector of the post order traversal indices (the last pre order index
//     in its subtree) for each vertex
//   vert: vector of vertex for each pre order index
// Functions:
//   lca(v, w): returns the lowest common ancestor of vertices v and w assuming
//     v and w are connected
//   connected(v, w): returns true if and only if v and w are connected
//   dist(v, w): returns the distance between vertices v and w assuming
//     v and w are connected
//   kthParent(v, k): returns the kth parent of the vertex v (0th parent is v,
//     1st parent is the parent of v)
//   kthPath(v, w, k): returns the kth vertex (0-indexed) on the path from
//     v to w
//   getChains(v, w, edgeChains): returns a tuple of left index, right index,
//     and a boolean indicating the ranges of the chains on the path from v to
//     w and whether the range is reversed, with the chains being provided in
//     order from v to w, with the lca of v and w being included if edgeChains
//     is false, and excluded if it is true
// In practice, constructor has a moderate constant,
//   lca, dist, kthParent, kthPath, have a small constant
// Time Complexity:
//   constructor: O(V)
//   lca, dist, kthParent, kthPath: O(log V)
//   connected: O(1)
// Memory Complexity: O(V)
// Tested:
//   https://www.spoj.com/problems/QTREE2/
//   https://www.spoj.com/problems/GSS7/
//   https://judge.yosupo.jp/problem/vertex_set_path_composite
struct HLD {
  int V, ind; vector<int> root, dep, par, size, head, pre, post, vert;
  template <class Forest>
  void dfs(const Forest &G, int v, int prev, int r, int d) {
    root[v] = r; dep[v] = d; par[v] = prev; size[v] = 1; for (int w : G[v])
      if (w != prev) { dfs(G, w, v, r, d + 1); size[v] += size[w]; }
  }
  template <class Forest> void hld(const Forest &G, int v, int prev) {
    if (head[v] == -1) head[v] = v;
    vert[pre[v] = ++ind] = v; int heavy = -1;
    for (int w : G[v]) if (w != prev && (heavy == -1 || size[heavy] < size[w]))
      heavy = w;
    if (heavy != -1) { head[heavy] = head[v]; hld(G, heavy, v); }
    for (int w : G[v]) if (w != prev && w != heavy) hld(G, w, v);
    post[v] = ind;
  }
  int lca(int v, int w) {
    while (head[v] != head[w]) {
      if (dep[head[v]] < dep[head[w]]) w = par[head[w]];
      else v = par[head[v]];
    }
    return dep[v] < dep[w] ? v : w;
  }
  int dist(int v, int w) { return dep[v] + dep[w] - 2 * dep[lca(v, w)]; }
  int kthParent(int v, int k) {
    while (par[head[v]] != -1) {
      if (pre[v] - pre[head[v]] >= k) return vert[pre[v] - k];
      k -= pre[v] - pre[head[v]] + 1; v = par[head[v]];
    }
    return pre[v] < k ? -1 : vert[pre[v] - k];
  }
  int kthPath(int v, int w, int k) {
    int LCA = lca(v, w);
    if (dep[v] - dep[LCA] >= k) return kthParent(v, k);
    else return kthParent(w, dep[v] + dep[w] - 2 * dep[LCA] - k);
  }
  bool connected(int v, int w) { return root[v] == root[w]; }
  vector<tuple<int, int, bool>> getChains(int v, int w, bool edgeChains) {
    vector<tuple<int, int, bool>> vChains, wChains;
    while (head[v] != head[w]) {
      if (dep[head[v]] < dep[head[w]]) {
        wChains.emplace_back(pre[head[w]], pre[w], false); w = par[head[w]];
      } else {
        vChains.emplace_back(pre[head[v]], pre[v], true); v = par[head[v]];
      }
    }
    if (v != w) {
      if (dep[v] < dep[w])
        wChains.emplace_back(pre[v] + edgeChains, pre[w], false);
      else vChains.emplace_back(pre[w] + edgeChains, pre[v], true);
    } else if (!edgeChains) {
      int i = pre[dep[v] < dep[w] ? v : w]; wChains.emplace_back(i, i, false);
    }
    reverse(wChains.begin(), wChains.end());
    vChains.insert(vChains.end(), wChains.begin(), wChains.end());
    return vChains;
  }
  template <class Forest>
  HLD(const Forest &G, const vector<int> &roots = vector<int>())
      : V(G.size()), ind(-1), root(V, -1), dep(V), par(V), size(V),
        head(V, -1), pre(V), post(V), vert(V) {
    if (roots.empty()) {
      for (int v = 0; v < V; v++)
        if (root[v] == -1) { dfs(G, v, -1, v, 0); hld(G, v, -1); }
    } else for (int v : roots) { dfs(G, v, -1, v, 0); hld(G, v, -1); }
  }
  template <class Forest> HLD(const Forest &G, int rt)
      : HLD(G, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "LowestCommonAncestor.h"
using namespace std;

// Mo's algorithm on a tree to answer offline queries over paths on a forest
//   where each vertex has a value provided by an array A
// Template Arguments:
//   S: struct to maintain a multiset of the elements in a set
//   Required Fields:
//     T: the type of each element
//     R: the type of the return value for each query
//     Q: the query object that contains information for each query
//       Required Fields:
//         v: one vertex of the query path
//         w: the other vertex of the query path
//   Required Functions:
//     constructor(...args): takes any number of arguments (arguments are
//       passed from constructor of MoTree)
//     add(v): adds the value v to the multiset
//     remove(v): removes the value v from the multiset
//   Sample Struct: supporting queries for whether a value c exists on
//       a path between vertices v and w
//     struct S {
//       using T = int; using R = bool;
//       struct Q { int v, w, c; };
//       vector<T> cnt;
//       S(const vector<T> &A)
//           : cnt(*max_element(A.begin(), A.end()) + 1, 0) {}
//       void add(const T &v) { cnt[v]++; }
//       void remove(const T &v) { --cnt[v]; }
//       R query(const Q &q) const {
//         return 0 <= q.c && q.c < int(cnt.size()) && cnt[q.c] > 0;
//       }
//     };
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type S::T of the values in the array
//   queries: a vector of type S::Q representing the queries
//   SCALE: the value to scale sqrt by
//   ...args: arguments to pass to the constructor of S
// Fields:
//   ans: a vector of integers with the answer for each query
// In practice, has a very small constant
// Time Complexity:
//   constructor: O(C + K ((log K + U sqrt V) + T))
//     for K queries where C is the time complexity of S's constructor,
//     U is the time complexity of S.add and S.remove,
//     and T is the time complexity of S.query
// Memory Complexity: O(V + K) for K queries
// Tested:
//   https://www.spoj.com/problems/COT2/
//   https://www.spoj.com/problems/GOT/
//   https://dmoj.ca/problem/year2018p6
template <class S> struct MoTree {
  using T = typename S::T; using R = typename S::R; using Q = typename S::Q;
  struct Query {
    Q q; int l, r, lca, i, b;
    Query(const Q &q, int l, int r, int lca, int i, int b)
        : q(q), l(l), r(r), lca(lca), i(i), b(b) {}
    pair<int, int> getPair() const { return make_pair(b, b % 2 ? -r : r); }
    bool operator < (const Query &o) const { return getPair() < o.getPair(); }
  };
  int V, ind; vector<int> pre, post, vert; LCA<> lca; vector<R> ans;
  template <class Forest> void dfs(const Forest &G, int v, int prev) {
    vert[pre[v] = ind++] = v; for (int w : G[v]) if (w != prev) dfs(G, w, v);
    vert[post[v] = ind++] = v;
  }
  template <class Forest> LCA<> init(const Forest &G) {
    vector<int> roots; for (int v = 0; v < V; v++)
      if (pre[v] == -1) { roots.push_back(v); dfs(G, v, -1); }
    return LCA<>(G, roots);
  }
  template <class Forest, class ...Args> MoTree(
      const Forest &G, const vector<T> &A, const vector<Q> &queries,
      double SCALE = 2, Args &&...args)
      : V(G.size()), ind(0), pre(V, -1), post(V), vert(V * 2), lca(init(G)) {
    int K = queries.size(), bsz = max(1.0, sqrt(A.size()) * SCALE);
    vector<Query> q; q.reserve(K); vector<bool> vis(V, false);
    S s(forward<Args>(args)...); for (int i = 0; i < K; i++) {
      int v = queries[i].v, w = queries[i].w, u = lca.lca(v, w);
      if (pre[v] > pre[w]) swap(v, w);
      int l = u == v ? pre[v] : post[v], r = pre[w];
      q.emplace_back(queries[i], l, r, u, i, l / bsz);
    }
    auto update = [&] (int v) {
      if (vis[v]) s.remove(A[v]);
      else s.add(A[v]);
      vis[v] = !vis[v];
    };
    sort(q.begin(), q.end()); int l = 0, r = l - 1; for (auto &&qi : q) {
      while (l > qi.l) update(vert[--l]);
      while (r < qi.r) update(vert[++r]);
      while (l < qi.l) update(vert[l++]);
      while (r > qi.r) update(vert[r--]);
      if (qi.lca != vert[l] && qi.lca != vert[r]) update(qi.lca);
      R res = s.query(qi.q); if (ans.empty()) ans.resize(K, res);
      ans[qi.i] = res;
      if (qi.lca != vert[l] && qi.lca != vert[r]) update(qi.lca);
    }
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "HeavyLightDecomposition.h"
using namespace std;

// Supports path (and subtree) queries on a forest
// Vertices and indices are 0-indexed
// Template Arguments:
//   R: struct supporting range queries on indices
//     Required Fields:
//       Data: the data type
//     Required Functions:
//       static qdef(): returns the query default value of type Data
//       static merge(l, r): merges the datas l and r, must be associative
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       query(l, r, rev): queries the range [l, r] with rev indicating
//         if the result needs to be reversed
//     Sample Struct: supporting range assignment and maximum subarray sum
//       struct R {
//         using Data = MaxSubarraySumCombine<int>::Data;
//         static Data qdef() { return MaxSubarraySumCombine<int>::qdef(); }
//         static Data merge(const Data &l, const Data &r) {
//           return MaxSubarraySumCombine<int>::merge(l, r);
//         }
//         SegmentTreeLazyBottomUp<MaxSubarraySumCombine<int>> ST;
//         R(const vector<Data> &A) : ST(A) {}
//         Data query(int l, int r, bool rev) {
//           Data ret = ST.query(l, r);
//           if (rev) swap(ret.pre, ret.suf);
//           return ret;
//         }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type R::Data with the initial value of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Functions:
//   queryPath(v, w): queries the path from v to w
//   querySubtree(v): queries the subtree of vertex v
// In practice, constructor has a moderate constant,
//   query functions have a small constant
// Time Complexity:
//   constructor: O(V) + time complexity of R's constructor
//   queryPath: O(log V) + time complexity of R's query
//   querySubtree: time complexity of R's query
// Memory Complexity: O(V) + memory complexity of R
// Tested:
//   https://dmoj.ca/problem/acc2p3
template <class R, const bool VALUES_ON_EDGES>
struct StaticPathQueries : public HLD {
  using Data = typename R::Data; R ops; vector<Data> down, up;
  Data queryPath(int v, int w) {
    Data qu = R::qdef(), qd = R::qdef(); while (head[v] != head[w]) {
      if (dep[head[v]] < dep[head[w]]) {
        qd = R::merge(down[w], qd); w = par[head[w]];
      } else { qu = R::merge(qu, up[v]); v = par[head[v]]; }
    }
    if (v != w) {
      if (dep[v] < dep[w])
        qu = R::merge(qu, ops.query(pre[v] + VALUES_ON_EDGES, pre[w], false));
      else
        qd = R::merge(ops.query(pre[w] + VALUES_ON_EDGES, pre[v], true), qd);
    } else if (!VALUES_ON_EDGES) {
      int i = pre[dep[v] < dep[w] ? v : w];
      qu = R::merge(qu, ops.query(i, i, false));
    }
    return R::merge(qu, qd);
  }
  Data querySubtree(int v) {
    int l = pre[v] + VALUES_ON_EDGES, r = post[v];
    return l <= r ? ops.query(l, r, false) : R::qdef();
  }
  vector<Data> reorder(const vector<Data> &A) {
    vector<Data> ret; ret.reserve(A.capacity());
    for (int i = 0; i < V; i++) ret.push_back(A[vert[i]]);
    return ret;
  }
  template <class Forest>
  StaticPathQueries(const Forest &G, const vector<Data> &A,
                    const vector<int> &roots = vector<int>())
      : HLD(G, roots), ops(reorder(A)), down(A), up(A) {
    for (int i = 0; i < V; i++) {
      int v = vert[i]; if (head[v] != v) {
        down[v] = R::merge(down[par[v]], A[v]);
        up[v] = R::merge(A[v], up[par[v]]);
      }
    }
  }
  template <class Forest>
  StaticPathQueries(const Forest &G, const vector<Data> &A, int rt)
      : StaticPathQueries(G, A, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/FischerHeunStructure.h"
#include "../../datastructures/unionfind/WeightedUnionFind.h"
using namespace std;

// Converts a tree or forest into a line graph to query for the maximum edge
//   value on a path between two vertices
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the weight of the edges
//   Cmp: the comparator to compare two values,
//       convention is same as std::priority_queue in STL
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   V: number of vertices in the graph
//   edges: a vector of tuples in the form (v, w, weight) representing
//     an undirected edge in the graph between vertices v and w with
//     weight of weight
//   cmp: an instance of the Cmp struct
// Functions:
//   connected(v, w): returns true if and only if v and w are connected
//   query(v, w): returns the maximum edge weight (based on the comparator) on
//     the path from vertices v and w assuming v and w are connected
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V)
//   connected, query: O(1)
// Memory Complexity: O(V)
// Tested:
//   https://dmoj.ca/problem/acc2p3
//   https://codeforces.com/problemsets/acmsguru/problem/99999/383
template <class T, class Cmp = less<T>> struct LineTree {
  using Edge = tuple<int, int, T>;
  vector<int> root, ind; vector<T> weights; FischerHeunStructure<int> FHS;
  vector<int> init(int V, vector<Edge> edges, Cmp cmp) {
    sort(edges.begin(), edges.end(), [&] (const Edge &a, const Edge &b) {
      return cmp(get<2>(a), get<2>(b));
    });
    vector<int> nxt(V, -1), A(V, 0), ret; ret.reserve(V); int k = 0;
    auto op = [&] (const pair<int, int> &a, const pair<int, int> &b) {
      nxt[a.second] = b.first; A[a.second] = k;
      return make_pair(a.first, b.second);
    };
    vector<pair<int, int>> W(V);
    for (int v = 0; v < V; v++) W[v] = make_pair(v, v);
    WeightedUnionFind<pair<int, int>, decltype(op)> uf(move(W), op);
    weights.reserve(edges.size()); for (auto &&e : edges) {
      assert(uf.join(get<0>(e), get<1>(e))); k++; weights.push_back(get<2>(e));
    }
    for (int v = 0; v < V; v++) if ((root[v] = uf.find(v)) == v)
      for (int w = uf.getWeight(v).first; w != -1; w = nxt[w]) {
        ind[w] = ret.size(); ret.push_back(A[w]);
      }
    return ret;
  }
  LineTree(int V, vector<Edge> edges, Cmp cmp = Cmp())
      : root(V), ind(V), weights(), FHS(init(V, move(edges), cmp)) {}
  bool connected(int v, int w) { return root[v] == root[w]; }
  T query(int v, int w) {
    assert(v != w); if (ind[v] > ind[w]) swap(v, w);
    return weights[FHS.query(ind[v], ind[w] - 1)];
  }
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/BitPrefixSumArray.h"
#include "HeavyLightDecomposition.h"
using namespace std;

// Wavelet Matrix supporting 2D aggregation path queries using heavy light
//   decomposition on a forest where the data can change, but not the keys
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the element of the array
//   R: struct supporting point updates and prefix queries on indices
//     Required Fields:
//       Data: the data type
//       Lazy: the lazy type
//     Required Functions:
//       static qdef(): returns the query default value
//       static merge(l, r): returns the values l of type Data merged with
//         r of type Data, must be associative and commutative
//       constructor(A): takes a vector A of type Data with the initial
//         value of each index
//       update(i, val): updates the index i with the value val
//       query(l, r): queries the range [l, r]
//     Sample Struct: supporting point increments updates and
//         prefix sum queries
//       struct R {
//         using Data = int;
//         using Lazy = int;
//         static Data qdef() { return 0; }
//         static Data merge(const Data &l, const Data &r) { return l + r; }
//         FenwickTree1D<Data> FT;
//         R(const vector<Data> &A) : FT(A) {}
//         void update(int i, const Lazy &val) { FT.update(i, val); }
//         Data query(int l, int r) { return FT.query(l, r); }
//       };
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
//   Cmp: the comparator to compare two elements
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type T of the values in the array
//   X: a vector of type R::Data containing the initial data of the array
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
//   cmp: an instance of the Cmp struct
// Functions:
//   update(v, val): updates the vertex v with the lazy value v
//   query(v, w, hi): returns the aggregate value of the data associated with
//     all elements with a key less than or equal to hi (using the comparator)
//     on the path from v to w
//   query(v, w, lo, hi): returns the aggregate value of the data associated
//     with all elements with a key of not less than lo and not greater than hi
//     (using the comparator) on the path from v to w
//   bsearch(v, w, f): over all keys in the array, finds the first key k such
//     that query(v, w, k) returns true
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O((V + C) log V) where C is the time complexity of
//     R's constructor
//   update: O(U log V) where U is the time complexity of R's update function
//   query, bsearch: O(Q (log V)^2) where Q is the time complexity of
//     R's query function
// Memory Complexity: O(V + (V log V) / 64 + M log V) where M is the memory
//   complexity of R
// Tested:
//   Fuzz and Stress Tested
template <class T, class R, const bool VALUES_ON_EDGES, class Cmp = less<T>>
struct WaveletMatrixHLD : public HLD {
#define clt [&] (const T &a, const T &b) { return cmp(a, b); }
#define cle [&] (const T &a, const T &b) { return !cmp(b, a); }
  using Data = typename R::Data; using Lazy = typename R::Lazy;
  int H; vector<int> mid; vector<T> S; vector<BitPrefixSumArray> B;
  vector<R> D; Cmp cmp;
  template <class Forest>
  WaveletMatrixHLD(const Forest &G, const vector<T> &A, const vector<Data> &X,
                   const vector<int> &roots = vector<int>(), Cmp cmp = Cmp())
      : HLD(G, roots), H(V == 0 ? 0 : __lg(V) + 1), mid(H), S(A),
        B(H, BitPrefixSumArray(V)), cmp(cmp) {
    sort(S.begin(), S.end(), cmp); vector<int> temp(V), C(V), P(V);
    vector<Data> Y = X, Z = X; D.reserve(H); for (int v = 0; v < V; v++)
      temp[v] = lower_bound(S.begin(), S.end(), A[v], cmp) - S.begin();
    for (int v = 0; v < V; v++) { C[pre[v]] = temp[v]; Y[pre[v]] = X[v]; }
    iota(P.begin(), P.end(), 0); for (int h = H - 1; h >= 0; h--) {
      int ph = 1 << h;
      for (int i = 0; i < V; i++) B[h].set(i, C[P[i]] <= ph - 1);
      mid[h] = stable_partition(P.begin(), P.end(), [&] (int i) {
                                  return C[i] <= ph - 1;
                                }) - P.begin();
      B[h].build(); for (int i = 0; i < V; i++) Z[i] = Y[P[i]];
      D.emplace_back(Z); for (int i = mid[h]; i < V; i++) C[P[i]] -= ph;
    }
    reverse(D.begin(), D.end());
  }
  template <class Forest>
  WaveletMatrixHLD(const Forest &G, const vector<T> &A,
                   const vector<Data> &X, int rt, Cmp cmp = Cmp())
      : WaveletMatrixHLD(G, A, X, vector<int>{rt}, cmp) {}
  using Ranges = vector<tuple<int, int, int, int>>;
  Ranges getRanges(int v, int w) {
    Ranges ranges; while (head[v] != head[w]) {
      if (dep[head[v]] < dep[head[w]]) {
        ranges.emplace_back(pre[head[w]], pre[w], 0, 0); w = par[head[w]];
      } else {
        ranges.emplace_back(pre[head[v]], pre[v], 0, 0); v = par[head[v]];
      }
    }
    if (v != w) {
      if (dep[v] < dep[w])
        ranges.emplace_back(pre[v] + VALUES_ON_EDGES, pre[w], 0, 0);
      else ranges.emplace_back(pre[w] + VALUES_ON_EDGES, pre[v], 0, 0);
    } else if (!VALUES_ON_EDGES) {
      int i = pre[dep[v] < dep[w] ? v : w]; ranges.emplace_back(i, i, 0, 0);
    }
    return ranges;
  }
  void update(int v, const Lazy &val) {
    for (int i = pre[v], h = H - 1; h >= 0; h--) {
      if (B[h].get(i)) i = B[h].query(i - 1);
      else i += mid[h] - B[h].query(i - 1);
      D[h].update(i, val);
    }
  }
  void qryRanges(int h, Ranges &ranges) {
    for (auto &&r : ranges) {
      get<2>(r) = B[h].query(get<0>(r) - 1); get<3>(r) = B[h].query(get<1>(r));
    }
  }
  Data qryAggLeft(int h, const Ranges &ranges) {
    Data ret = R::qdef(); for (auto &&r : ranges) {
      int a = get<2>(r), b = get<3>(r) - 1;
      if (a <= b) ret = R::merge(ret, D[h].query(a, b));
    }
    return ret;
  }
  Data qryAggRight(int h, const Ranges &ranges) {
    Data ret = R::qdef(); for (auto &&r : ranges) {
      int a = get<0>(r) + mid[h] - get<2>(r);
      int b = get<1>(r) + mid[h] - get<3>(r);
      if (a <= b) ret = R::merge(ret, D[h].query(a, b));
    }
    return ret;
  }
  void left(Ranges &ranges) {
    for (auto &&r : ranges) {
      get<0>(r) = get<2>(r); get<1>(r) = get<3>(r) - 1;
    }
  }
  void right(int h, Ranges &ranges) {
    for (auto &&r : ranges) {
      get<0>(r) += mid[h] - get<2>(r); get<1>(r) += mid[h] - get<3>(r);
    }
  }
  template <class F>
  Data qryPre(int h, int cur, Ranges &ranges, const T &x, F f) {
    Data ret = R::qdef(); for (; h >= 0; h--) {
      int ph = 1 << h; qryRanges(h, ranges);
      if (cur + ph - 1 >= V || f(x, S[cur + ph - 1])) left(ranges);
      else {
        ret = R::merge(ret, qryAggLeft(h, ranges));
        cur += ph; right(h, ranges);
      }
    }
    return ret;
  }
  template <class F>
  Data qrySuf(int h, int cur, Ranges &ranges, const T &v, F f) {
    Data ret = R::qdef(); for (; h >= 0; h--) {
      int ph = 1 << h; qryRanges(h, ranges);
      if (cur + ph - 1 >= V || f(v, S[cur + ph - 1])) {
        ret = R::merge(ret, qryAggRight(h, ranges));
        if (h == 0) ret = R::merge(ret, qryAggLeft(h, ranges));
        left(ranges);
      } else {
        if (h == 0) ret = R::merge(ret, qryAggRight(h, ranges));
        cur += ph; right(h, ranges);
      }
    }
    return ret;
  }
  Data query(int v, int w, const T &hi) {
    Ranges ranges = getRanges(v, w); return qryPre(H - 1, 0, ranges, hi, clt);
  }
  Data query(int v, int w, const T &lo, const T &hi) {
    Ranges ranges = getRanges(v, w);
    for (int cur = 0, h = H - 1; h >= 0; h--) {
      int ph = 1 << h; qryRanges(h, ranges);
      bool loLeft = cur + ph - 1 >= V || !cmp(S[cur + ph - 1], lo);
      bool hiLeft = cur + ph - 1 >= V || cmp(hi, S[cur + ph - 1]);
      if (loLeft != hiLeft) {
        Ranges leftRanges = ranges, rightRanges = ranges;
        left(leftRanges); right(h, rightRanges);
        Data ret = R::merge(qrySuf(h - 1, cur, leftRanges, lo, cle),
                            qryPre(h - 1, cur + ph, rightRanges, hi, clt));
        return h == 0 ? R::merge(ret, qryAggLeft(h, ranges)) : ret;
      } else if (loLeft) left(ranges);
      else { cur += ph; right(h, ranges); }
    }
    return R::qdef();
  }
  template <class F> pair<bool, T *> bsearch(int v, int w, F f) {
    int cur = 0; Data agg = R::qdef(); Ranges ranges = getRanges(v, w);
    for (int h = H - 1; h >= 0; h--) {
      qryRanges(h, ranges); Data val = qryAggLeft(h, ranges);
      if (f(R::merge(agg, val))) left(ranges);
      else { cur += 1 << h; agg = R::merge(agg, val); right(h, ranges); }
    }
    return make_pair(cur < V, cur < V ? &S[cur] : nullptr);
  }
#undef clt
#undef cle
};


text:
#pragma once
#include <bits/stdc++.h>
#include "LowestCommonAncestor.h"
#include "SubtreeQueries.h"
using namespace std;

// Supports online queries for the number of distinct elements in a
//   subtree for a static forest G with V vertices
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of each element
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type T of the values of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
// Functions:
//   query(v): returns the number of distinct elements in the subtree of
//     vertex v
// In practice, has a moderate constant, slightly faster than SmallToLargeTree
// Time Complexity:
//   constructor: O(V log V)
//   query: O(1)
// Memory Complexity: O(V)
// Tested:
//   https://cses.fi/problemset/task/1139/
template <class T> struct CountDistinctSubtree {
  struct R {
    using Data = int; using Lazy = int; vector<Data> A;
    static Data qdef() { return 0; }
    R(vector<Data> A) : A(move(A)) {}
    void update(int l, int, const Lazy &val) { A[l] += val; }
    Data query(int l, int r) { return A[r] - (l == 0 ? 0 : A[l - 1]); }
  };
  LCA<> lca; SubtreeQueries<R, false> sbtr;
  int query(int v) { return sbtr.querySubtree(v); }
  template <class Forest>
  CountDistinctSubtree(const Forest &G, const vector<T> &A,
                       const vector<int> &roots = vector<int>())
      : lca(G, roots), sbtr(G, vector<int>(A.size(), 0), roots) {
    int V = G.size(); vector<T> temp = A; sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    vector<int> C(V), st(temp.size() + 1, 0), ind(V);
    for (int v = 0; v < V; v++)
      st[C[v] = lower_bound(temp.begin(), temp.end(), A[v]) - temp.begin()]++;
    partial_sum(st.begin(), st.end(), st.begin());
    for (int v : sbtr.vert) ind[--st[C[v]]] = v;
    for (int i = 0; i < int(temp.size()); i++)
      for (int j = st[i]; j < st[i + 1]; j++) {
        sbtr.updateVertex(ind[j], 1); if (j + 1 < st[i + 1])
          sbtr.updateVertex(lca.lca(ind[j], ind[j + 1]), -1);
      }
    partial_sum(sbtr.ops.A.begin(), sbtr.ops.A.end(), sbtr.ops.A.begin());
  }
  template <class Forest>
  CountDistinctSubtree(const Forest &G, const vector<T> &A, int rt)
      : CountDistinctSubtree(G, A, vector<int>{rt}) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/trees/fenwicktrees/FenwickTree1D.h"
#include "LowestCommonAncestor.h"
#include "SubtreeQueries.h"
using namespace std;

// Supports online queries for the number of distinct elements in a
//   subtree for a forest G with V vertices with vertex updates
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of each element
//   C: a container representing a mapping from type T to a set of integers
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type T of the intial values of each vertex
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
//   ...args: arguments to pass to the constructor of an instance of type C
// Functions:
//   update(v, val): update vertex v with the value val
//   query(v): returns the number of distinct elements in the subtree of
//     vertex v
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V log V)
//   update, query: O(log V)
// Memory Complexity: O(V)
// Tested:
//   https://dmoj.ca/problem/dmopc20c1p5
template <class T, class C = map<T, set<int>>>
struct CountDistinctSubtreeUpdates {
  struct R {
    using Data = int; using Lazy = int; FenwickTree1D<Data> FT;
    static Data qdef() { return 0; }
    R(vector<Data> A) : FT(move(A)) {}
    void update(int l, int, const Lazy &val) { FT.update(l, val); }
    Data query(int l, int r) { return FT.query(l, r); }
  };
  vector<T> A; C M; LCA<> lca; SubtreeQueries<R, false> sbtr;
  void upd(int v, const T &val, int delta) {
    int u = -1, w = -1; set<int> &mv = M[val];
    auto it = delta == 1 ? mv.upper_bound(sbtr.pre[v])
                         : mv.erase(mv.find(sbtr.pre[v]));
    if (it != mv.begin())
      sbtr.updateVertex(lca.lca(u = sbtr.vert[*prev(it)], v), -delta);
    if (it != mv.end())
      sbtr.updateVertex(lca.lca(v, w = sbtr.vert[*it]), -delta);
    if (u != -1 && w != -1) sbtr.updateVertex(lca.lca(u, w), delta);
    sbtr.updateVertex(v, delta); if (delta == 1) mv.insert(it, sbtr.pre[v]);
  }
  void update(int v, const T &val) { upd(v, A[v], -1); upd(v, A[v] = val, 1); }
  int query(int v) { return sbtr.querySubtree(v); }
  vector<int> init(int V) {
    vector<int> ret; ret.reserve(V + 1); ret.resize(V, 0); return ret;
  }
  template <class Forest, class ...Args> CountDistinctSubtreeUpdates(
      const Forest &G, const vector<T> &A,
      const vector<int> &roots = vector<int>(), Args &&...args)
      : A(A), M(forward<Args>(args)...),
        lca(G, roots), sbtr(G, init(A.size()), roots) {
    for (int v = 0; v < int(G.size()); v++) upd(v, A[v], 1);
  }
  template <class Forest, class ...Args>
  CountDistinctSubtreeUpdates(const Forest &G, const vector<T> &A, int rt,
                              Args &&...args)
      : CountDistinctSubtreeUpdates(G, A, vector<int>{rt},
                                    forward<Args>(args)...) {}
};


text:
#pragma once
#include <bits/stdc++.h>
#include "../../datastructures/BitPrefixSumArray.h"
#include "LowestCommonAncestor.h"
using namespace std;

// Wavelet Matrix supporting rank and select operations for paths on a forest
// Vertices are 0-indexed
// Template Arguments:
//   T: the type of the element of the array
//   VALUES_ON_EDGES: boolean indicating whether the values are on the edges
//     (the largest depth vertex of the edge) or the vertices
//   Cmp: the comparator to compare two elements
//     Required Functions:
//       operator (a, b): returns true if and only if a compares less than b
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type T of the values in the array
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
//   cmp: an instance of the Cmp struct
// Functions:
//   rank(v, w, x): returns the number of values less than k (using the
//     comparator) on the path from v to w
//   count(v, w, lo, hi) returns the number of values not less than lo and
//     not greater than hi (using the comparator) on the path from v to w
//   select(v, w, k): returns the kth element (0-indexed) sorted by the
//     comparator if the values on the the path from v to w were sorted
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(V log V)
//   rank, count, select: O(log V)
// Memory Complexity: O(V + (V log V) / 64)
// Tested:
//   https://mcpt.ca/problem/hld2 (rank/count)
//   https://www.acmicpc.net/problem/11932 (select)
template <class T, const bool VALUES_ON_EDGES, class Cmp = less<T>>
struct WaveletMatrixTree {
#define clt [&] (const T &a, const T &b) { return cmp(a, b); }
#define cle [&] (const T &a, const T &b) { return !cmp(b, a); }
  int V, H, preInd, postInd; vector<int> par, pre, post, last, mid1, mid2;
  vector<T> S; LCA<> lca; vector<BitPrefixSumArray> B1, B2; Cmp cmp;
  template <class Forest> void dfs(const Forest &G, int v, int prev) {
    par[v] = prev; last[pre[v] = preInd++] = postInd - 1;
    for (int w : G[v]) if (w != prev) dfs(G, w, v);
    post[v] = postInd++;
  }
  void build(const vector<int> &A, const vector<int> &ind, vector<int> &mid,
             vector<BitPrefixSumArray> &B) {
    vector<int> C(V); for (int v = 0; v < V; v++) C[ind[v]] = A[v];
    for (int h = H - 1; h >= 0; h--) {
      int ph = 1 << h; for (int i = 0; i < V; i++) B[h].set(i, C[i] <= ph - 1);
      mid[h] = stable_partition(C.begin(), C.end(), [&] (int v) {
                                  return v <= ph - 1;
                                }) - C.begin();
      B[h].build(); for (int i = mid[h]; i < V; i++) C[i] -= ph;
    }
  }
  template <class Forest>
  WaveletMatrixTree(const Forest &G, const vector<T> &A,
                    const vector<int> &roots = vector<int>(), Cmp cmp = Cmp())
      : V(A.size()), H(V == 0 ? 0 : __lg(V) + 1), preInd(0), postInd(0),
        par(V, -1), pre(V), post(V), last(V), mid1(H), mid2(H),
        S(A), lca(G, roots), B1(H, BitPrefixSumArray(V)), B2(B1), cmp(cmp) {
    sort(S.begin(), S.end(), cmp); if (roots.empty()) {
      for (int v = 0; v < V; v++) if (par[v] == -1) dfs(G, v, -1);
    } else for (int v : roots) dfs(G, v, -1);
    vector<int> C(V); for (int v = 0; v < V; v++)
      C[v] = lower_bound(S.begin(), S.end(), A[v], cmp) - S.begin();
    build(C, pre, mid1, B1); build(C, post, mid2, B2);
  }
  template <class Forest>
  WaveletMatrixTree(const Forest &G, const vector<T> &A, int rt,
                    Cmp cmp = Cmp())
      : WaveletMatrixTree(G, A, vector<int>{rt}, cmp) {}
  bool connected(int v, int w) { return lca.connected(v, w); }
  using Ranges = vector<tuple<int, int, int, int, int>>;
  Ranges getRanges(int v, int w) {
    int u = lca.lca(v, w), rt = lca.root[v]; Ranges ranges; ranges.reserve(5);
    int t = VALUES_ON_EDGES ? 1 : (par[u] != -1 ? 2 : 0);
    if (t && pre[rt] - 1 > 0)
      ranges.emplace_back(pre[rt] - 1, last[pre[rt] - 1], -1, 0, 0);
    ranges.emplace_back(pre[v], last[pre[v]], 1, 0, 0);
    ranges.emplace_back(pre[w], last[pre[w]], 1, 0, 0);
    ranges.emplace_back(pre[u], last[pre[u]], t == 1 ? -2 : -1, 0, 0);
    if (t == 2) ranges.emplace_back(pre[par[u]], last[pre[par[u]]], -1, 0, 0);
    return ranges;
  }
  int query(int h, Ranges &ranges) {
    int val = 0; for (auto &&r : ranges) {
      get<3>(r) = B1[h].query(get<0>(r)); get<4>(r) = B2[h].query(get<1>(r));
      val += get<2>(r) * (get<3>(r) - get<4>(r));
    }
    return val;
  }
  void left(Ranges &ranges) {
    for (auto &&r : ranges) {
      get<0>(r) = get<3>(r) - 1; get<1>(r) = get<4>(r) - 1;
    }
  }
  void right(int h, Ranges &ranges) {
    for (auto &&r : ranges) {
      get<0>(r) += mid1[h] - get<3>(r); get<1>(r) += mid2[h] - get<4>(r);
    }
  }
  template <class F> int cnt(int v, int w, const T &x, F f) {
    Ranges ranges = getRanges(v, w);
    int ret = 0; for (int cur = 0, h = H - 1; h >= 0; h--) {
      int ph = 1 << h, val = query(h, ranges);
      if (cur + ph - 1 >= V || f(x, S[cur + ph - 1])) left(ranges);
      else { cur += ph; ret += val; right(h, ranges); }
    }
    return ret;
  }
  int rank(int v, int w, const T &x) { return cnt(v, w, x, cle); }
  int count(int v, int w, const T &lo, const T &hi) {
    return cnt(v, w, hi, clt) - cnt(v, w, lo, cle);
  }
  T select(int v, int w, int k) {
    Ranges ranges = getRanges(v, w);
    int cur = 0; for (int h = H - 1; h >= 0; h--) {
      int val = query(h, ranges); if (k < val) left(ranges);
      else { cur += 1 << h; k -= val; right(h, ranges); }
    }
    return S[cur];
  }
#undef clt
#undef cle
};


text:
#pragma once
#include <bits/stdc++.h>
using namespace std;

// Supports queries on graphs that involve the set of vertices in a subtree
// Template Arguments:
//   S: struct to maintain a multiset of the elements in a set
//   Required Fields:
//     T: the type of each element
//     R: the type of the return value for each query
//     Q: the query object that contains information for each query
//       Required Fields:
//         v: the vertex of the subtree to query
//   Required Functions:
//     constructor(A): takes a vector A of type T equal to the static array
//       representing the values for each vertex of the graph
//     add(v): adds the value v to the multiset
//     remove(v): removes the value v from the multiset
//   Sample Struct: supporting queries for whether a value c exists in
//       the subtree of vertex v
//     struct S {
//       using T = int; using R = bool;
//       struct Q { int v, c; };
//       vector<T> cnt;
//       S(const vector<T> &A)
//           : cnt(*max_element(A.begin(), A.end()) + 1, 0) {}
//       void add(const T &v) { cnt[v]++; }
//       void remove(const T &v) { --cnt[v]; }
//       R query(const Q &q) const {
//         return 0 <= q.c && q.c < int(cnt.size()) && cnt[q.c] > 0;
//       }
//     };
// Constructor Arguments:
//   G: a generic forest data structure
//     Required Functions:
//       operator [v] const: iterates over the adjacency list of vertex v
//         (which is a list of ints)
//       size() const: returns the number of vertices in the forest
//   A: a vector of type S::T of the values in the array
//   queries: a vector of type S::Q representing the queries
//   rt: a single root vertex
//   roots: a vector of root vertices for each connected component
//   f: a function from S::T to any arithmetic type, f(A[v]) needs to return
//     the weight of the vertex v with value A[v]
// Fields:
//   ans: a vector of integers with the answer for each query
// In practice, has a moderate constant
// Time Complexity:
//   constructor: O(C + U V log V + K T)
//     for K queries where C is the time complexity of S's constructor,
//     U is the time complexity of S.add and S.remove,
//     and T is the time complexity of S.query
// Memory Complexity: O(V + K) for K queries
// Tested:
//   https://cses.fi/problemset/task/1139/
//   https://codeforces.com/contest/600/problem/E
//   https://codeforces.com/contest/375/problem/D
template <class S> struct SmallToLargeTree {
  using T = typename S::T; using R = typename S::R; using Q = typename S::Q;
  vector<R> ans;
  template <class Forest, class F = function<int(T)>> SmallToLargeTree(
      const Forest &G, const vector<T> &A, const vector<Q> &queries,
      const vector<int> &roots = vector<int>(), F f = [] (T) { return 1; } ) {
    using weight_t = decltype(f(T())); int V = G.size(), K = queries.size();
    vector<int> st(V + 1, 0), ind(K); S s(A);
    vector<weight_t> size(V, weight_t());
    function<void(int, int)> getSize = [&] (int v, int prev) {
      size[v] = f(A[v]);
      for (int w : G[v]) if (w != prev) { getSize(w, v); size[v] += size[w]; }
    };
    function<void(int, int, int, bool)> update = [&] (
        int v, int prev, int heavy, bool add) {
      if (add) s.add(A[v]);
      else s.remove(A[v]);
      for (int w : G[v]) if (w != prev && w != heavy) update(w, v, heavy, add);
    };
    function<void(int, int, bool)> dfs = [&] (int v, int prev, bool keep) {
      int heavy = -1; for (int w : G[v])
        if (w != prev && (heavy == -1 || size[heavy] < size[w])) heavy = w;
      for (int w : G[v]) if (w != prev && w != heavy) dfs(w, v, 0);
      if (heavy != -1) dfs(heavy, v, 1);
      update(v, prev, heavy, 1); for (int i = st[v]; i < st[v + 1]; i++) {
        R res = s.query(queries[ind[i]]); if (ans.empty()) ans.resize(K, res);
        ans[ind[i]] = res;
      }
      if (!keep) update(v, prev, -1, 0);
    };
    for (int i = 0; i < K; i++) st[queries[i].v]++;
    partial_sum(st.begin(), st.end(), st.begin());
    for (int i = 0; i < K; i++) ind[--st[queries[i].v]] = i;
    if (roots.empty()) {
      for (int v = 0; v < V; v++)
        if (size[v] == weight_t()) { getSize(v, -1); dfs(v, -1, 0); }
    } else for (int v : roots) { getSize(v, -1); dfs(v, -1, 0); }
  }
  template <class Forest, class F = function<int(T)>> SmallToLargeTree(
      const Forest &G, const vector<T> &A, const vector<Q> &queries, int rt,
      F f = [] (T) { return 1; })
      : SmallToLargeTree(G, A, queries, vector<int>{rt}, f) {}
};