lmori's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub lmorinn/library

:heavy_check_mark: verify/LibraryChecker/graph/tree/VertexAddSubtreeSum.test.cpp

Depends on

Code

#include "../../../../template/template.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#include "../../../../data-structure/binary-indexed-tree/BinaryIndexedTree.hpp"
#include "../../../../graph/tree/HLD.hpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  in(n, q);
  hld t(n);
  fenwick_tree<lint> f(n);
  vector<int> a(n);

  in(a);
  rep(i, 1, n) {
    int p;
    in(p);
    t.add_edge(i, p);
  }

  rep(i, n) f.add(t.traverse_begin(i), a[i]);
  rep(i, q) {
    int com;
    in(com);
    if (com == 0) {
      int u, x;
      in(u, x);
      f.add(t.traverse_begin(u), x);
    } else {
      int u;
      in(u);
      out(f.sum(t.traverse_begin(u), t.traverse_end(u)));
    }
  }
}
#line 2 "template/template.hpp"
#pragma region Macros
#include <bits/stdc++.h>
#include <tr2/dynamic_bitset>

using namespace std;
using namespace tr2;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define logfixed(x) cout << fixed << setprecision(10) << x << endl;

ostream &operator<<(ostream &dest, __int128_t value) {
  ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(ios_base::badbit);
    }
  }
  return dest;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (int i = 0; i < (int)v.size(); i++) {
    os << v[i] << (i + 1 != (int)v.size() ? " " : "");
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &set_var) {
  for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
    os << *itr;
    ++itr;
    if (itr != set_var.end()) os << " ";
    itr--;
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const unordered_map<T, U> &map_var) {
  for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
    os << itr->first << " -> " << itr->second << "\n";
  }
  return os;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
  os << pair_var.first << " " << pair_var.second;
  return os;
}

void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
  cout << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

void outf() { cout << '\n'; }
template <class T, class... Ts>
void outf(const T &a, const Ts &...b) {
  cout << fixed << setprecision(14) << a;
  (cout << ... << (cout << ' ', b));
  cout << '\n';
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &in : v) is >> in;
  return is;
}

inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
  cin >> first;
  in(rest...);
  return;
}

template <typename T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};

#pragma endregion
#line 2 "verify/LibraryChecker/graph/tree/VertexAddSubtreeSum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_subtree_sum"
#line 1 "data-structure/binary-indexed-tree/BinaryIndexedTree.hpp"

template <class T>
struct fenwick_tree {
   public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        p++;
        while (p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        return sum(r) - sum(l);
    }

   private:
    int _n;
    vector<T> data;

    T sum(int r) {
        T s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};
#line 1 "graph/tree/HLD.hpp"

struct hld {
 private:
  int n, root, edge;
  vector<vector<int>> g;
  vector<int> heavy_p, heavy_l, light_p, idx, xdi, sub_siz;

  int dfs(int cur, int prev) {
    int sub = 1;
    for (int& nex : g[cur]) {
      if (nex == prev) {
        swap(g[cur].back(), nex);
        g[cur].pop_back();
        break;
      }
    }
    int best = 0;
    int idx = -1;
    for (int i = 0; i < int(g[cur].size()); i++) {
      int cnt = dfs(g[cur][i], cur);
      sub += cnt;
      if (best < cnt) {
        best = cnt;
        idx = i;
      }
    }
    if (!g[cur].empty()) swap(g[cur][idx], g[cur].front());
    for (int i = 1; i < int(g[cur].size()); i++) light_p[g[cur][i]] = cur;
    sub_siz[cur] = sub;
    return sub;
  }

  void dfs2(int cur, int top, int& id) {
    heavy_p[cur] = top;
    idx[cur] = id;
    xdi[id] = cur;
    id++;
    if (!g[cur].empty()) {
      dfs2(g[cur].front(), top, id);
      heavy_l[cur] = heavy_l[g[cur].front()];
    } else {
      heavy_l[cur] = cur;
    }
    for (int i = 1; i < int(g[cur].size()); i++) dfs2(g[cur][i], g[cur][i], id);
  }

  void build() {
    int id = 0;
    dfs(root, -1);
    dfs2(root, root, id);
  }

 public:
  hld(int n, int root = 0) : n(n), root(root), edge(0), g(n), heavy_p(n, -1), heavy_l(n, -1), light_p(n, -1), idx(n), xdi(n), sub_siz(n) {}

  void add_edge(int u, int v) {
    g[u].emplace_back(v);
    g[v].emplace_back(u);
    edge++;
    if (edge == n - 1) build();
  }

  int lca(int u, int v) {
    while (heavy_p[u] != heavy_p[v]) {
      if (idx[u] > idx[v]) swap(u, v);
      v = light_p[heavy_p[v]];
    }
    return idx[u] < idx[v] ? u : v;
  }

  int dist(int u, int v) {
    int res = 0;
    while (heavy_p[u] != heavy_p[v]) {
      if (idx[u] > idx[v]) swap(u, v);
      res += idx[v] - idx[heavy_p[v]] + 1;
      v = light_p[heavy_p[v]];
    }
    res += abs(idx[u] - idx[v]);
    return res;
  }

  int meet(int r, int u, int v) {
    return lca(r, u) ^ lca(u, v) ^ lca(v, r);
  }

  int jump(int u, int v, int64_t d) {
    int from = u;
    int to = v;
    bool p = false;
    int ul_dist = 0;
    int lv_dist = 0;
    while (heavy_p[u] != heavy_p[v]) {
      if (idx[u] > idx[v]) {
        p = !p;
        swap(u, v);
        swap(ul_dist, lv_dist);
      }
      ul_dist += idx[v] - idx[heavy_p[v]] + 1;
      v = light_p[heavy_p[v]];
    }
    if (idx[u] > idx[v]) {
      p = !p;
      swap(u, v);
      swap(ul_dist, lv_dist);
    }
    ul_dist += idx[v] - idx[u];
    if (!p) {
      swap(ul_dist, lv_dist);
    }
    if (d <= ul_dist) {
      return la(from, d);
    }
    d -= ul_dist;
    if (d <= lv_dist) {
      return la(to, lv_dist - d);
    }
    return -1;
  }

  int la(int v, int64_t k) {
    while (v != -1) {
      int p = heavy_p[v];
      if (idx[v] - idx[p] >= k) {
        v = xdi[idx[v] - k];
        break;
      }
      k -= (idx[v] - idx[p] + 1);
      v = (p == root ? -1 : light_p[p]);
    }

    return v;
  }

  int subtree_size(int v) {
    return sub_siz[v];
  }

  int traverse_begin(int v) {
    return idx[v];
  }

  int traverse_end(int v) {
    return idx[v] + sub_siz[v];
  }

  bool contains_path(int from, int to, int v) {
    return meet(v, from, to) == v;
  }

  bool contains_subtree(int r, int v) {
    return traverse_begin(r) <= traverse_begin(v) and traverse_end(v) <= traverse_end(r);
  }

  pair<vector<int>, vector<int>> lca_based_auxiliary_tree(vector<int> v) {
    if (v.empty()) return {{}, {}};
    int siz = int(v.size());
    auto pre_order = [&](int i, int j) -> bool { return idx[i] < idx[j]; };
    sort(v.begin(), v.end(), pre_order);
    for (int i = 0; i < siz - 1; i++) v.emplace_back(lca(v[i], v[i + 1]));
    sort(v.begin(), v.end(), pre_order);
    v.erase(unique(v.begin(), v.end()), v.end());

    siz = int(v.size());
    vector<int> par(siz, -1);
    stack<int> st;
    st.emplace(0);
    for (int i = 1; i < siz; i++) {
      while (!st.empty() and traverse_end(v[st.top()]) <= traverse_begin(v[i])) st.pop();
      par[i] = st.top();
      st.push(i);
    }
    return {par, v};
  }
};
#line 5 "verify/LibraryChecker/graph/tree/VertexAddSubtreeSum.test.cpp"

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  in(n, q);
  hld t(n);
  fenwick_tree<lint> f(n);
  vector<int> a(n);

  in(a);
  rep(i, 1, n) {
    int p;
    in(p);
    t.add_edge(i, p);
  }

  rep(i, n) f.add(t.traverse_begin(i), a[i]);
  rep(i, q) {
    int com;
    in(com);
    if (com == 0) {
      int u, x;
      in(u, x);
      f.add(t.traverse_begin(u), x);
    } else {
      int u;
      in(u);
      out(f.sum(t.traverse_begin(u), t.traverse_end(u)));
    }
  }
}
Back to top page