ds/eulerTour2.cpp

View this file on GitHub
Last update: 2024-02-09 22:57:04+08:00

Verified with

test/vertex_add_subtree_sum.test.cpp

Code

//#include<segtree/segmentTree.cpp>

template<class M, M(*id)(), M(*op)(const M&, const M&)>
struct eulerTour2 {
  vector<int> tin, tout, p;
  segmentTree<M, id, op> st;

  eulerTour2(vector<vector<int>> g, int root = 0) : tin(ssize(g)), tout(ssize(g)), p(ssize(g), -1), st(ssize(g)) {
    int t = 0;
    auto dfs = [&](int v, auto self) -> void {
      tin[v] = t++;
      for(int x : g[v]) {
        if (x == p[v]) continue;
        p[x] = v;
        self(x, self);
      }
      tout[v] = t;
    };

    dfs(root, dfs);
  }

  void set(int v, M x) { st.set(tin[v], x); }
  M get(int v) { return st.get(tin[v]); }
  M query(int v) { return st.query(tin[v], tout[v]); }
};

#line 1 "ds/eulerTour2.cpp"
//#include<segtree/segmentTree.cpp>

template<class M, M(*id)(), M(*op)(const M&, const M&)>
struct eulerTour2 {
  vector<int> tin, tout, p;
  segmentTree<M, id, op> st;

  eulerTour2(vector<vector<int>> g, int root = 0) : tin(ssize(g)), tout(ssize(g)), p(ssize(g), -1), st(ssize(g)) {
    int t = 0;
    auto dfs = [&](int v, auto self) -> void {
      tin[v] = t++;
      for(int x : g[v]) {
        if (x == p[v]) continue;
        p[x] = v;
        self(x, self);
      }
      tout[v] = t;
    };

    dfs(root, dfs);
  }

  void set(int v, M x) { st.set(tin[v], x); }
  M get(int v) { return st.get(tin[v]); }
  M query(int v) { return st.query(tin[v], tout[v]); }
};