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/tree/VertexAddRangeContourSumonTree.test.cpp

Depends on

Code

#include "../../../template/template.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree"
#include "../../../atcoder/fenwicktree.hpp"
using namespace atcoder;
#include "../../../graph/tree/CentroidDecompositionContourSum.hpp"

using S = lint;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    in(n, q);
    vector<S> a(n);
    in(a);
    CentroidDecomposition<S> t(n);

    rep(i, n - 1) {
        int u, v;
        in(u, v);
        t.add_edge(u, v);
    }

    t.build(a);

    rep(i, q) {
        int com;
        in(com);
        if (com == 0) {
            int p;
            S x;
            in(p, x);
            t.add(p, x);
        } else {
            int p, l, r;
            in(p, l, r);
            out(t.prod(p, l, r));
        }
    }
}
#line 2 "template/template.hpp"
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
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/tree/VertexAddRangeContourSumonTree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree"
#line 1 "atcoder/fenwicktree.hpp"



#line 6 "atcoder/fenwicktree.hpp"

#line 1 "atcoder/internal_type_traits.hpp"



#line 6 "atcoder/internal_type_traits.hpp"
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder


#line 8 "atcoder/fenwicktree.hpp"

namespace atcoder {

// Reference: https://en.wikipedia.org/wiki/Fenwick_tree
template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;

  public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

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

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

  private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder


#line 4 "verify/LibraryChecker/tree/VertexAddRangeContourSumonTree.test.cpp"
using namespace atcoder;
#line 1 "graph/tree/CentroidDecompositionContourSum.hpp"
static const unsigned long long seed = chrono::steady_clock::now().time_since_epoch().count();
static mt19937_64 eng(seed);

template <class S>
class CentroidDecomposition {
   private:
    vector<vector<int>> g;
    vector<bool> dead;
    vector<S> leaf;
    vector<int> ord;
    vector<int> dinfo;
    vector<int> parent;
    vector<vector<fenwick_tree<S>>> subtrees;
    vector<vector<int>> ds_size;
    vector<int> subtree_size;
    vector<vector<pair<int, int>>> info;

    int n;
    int node_idx;

    void reorder(int s) {
        ord.assign(n, -1);
        queue<int> q;
        q.push(s);
        int idx = 0;
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            ord[cur] = idx++;
            for (int nex : g[cur])
                if (ord[nex] == -1) q.push(nex);
        }
    }

    S ds_prod(fenwick_tree<S> &fen, int siz, int l, int r) {
        l = max(0, l);
        r = min(r, siz);
        if (l < r) {
            return fen.sum(l, r);
        }
        return 0;
    }

   public:
    CentroidDecomposition(int siz) {
        n = siz;
        g.resize(n);

        node_idx = n;
    }
    CentroidDecomposition() {}

    void add_edge(int u, int v) {
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    void build(const vector<S> &a) {
        parent.assign(n << 1, -1);
        info.resize(n, vector<pair<int, int>>(30));
        subtrees.resize(n << 1, vector<fenwick_tree<S>>(2));
        ds_size.resize(n << 1, vector<int>(2));
        dead.resize(n, false);
        subtree_size.resize(n << 1);
        leaf.resize(n);
        dinfo.resize(n);
        reorder(uniform_int_distribution<int>(0, n - 1)(eng));
        vector<vector<int>> tmp(n);
        vector<int> par_cr(n << 1, -1);
        vector<int> head(n << 1);
        vector<int> tail(n << 1);
        vector<int> link(n << 1, -1);
        vector<S> d(n * 3);
        for (int i = 0; i < n; i++) {
            head[i] = tail[i] = i;
        }

        for (int u = 0; u < n; u++) {
            for (const int v : g[u]) {
                tmp[ord[u]].emplace_back(ord[v]);
            }
            leaf[ord[u]] = a[u];
        }
        g = tmp;

        function<int(int, int)> rec = [&](int start, int sz) -> int {
            int c = -1;
            const auto get_centroid = [&](auto &&self, int u, int p) -> void {
                subtree_size[u] = 1;
                for (const int v : g[u]) {
                    if (v == p || dead[v]) continue;

                    self(self, v, u);
                    if (v == c) {
                        subtree_size[u] = sz - subtree_size[c];
                        break;
                    }

                    subtree_size[u] += subtree_size[v];
                }

                if (c == -1 && subtree_size[u] * 2 > sz) c = u;
            };

            get_centroid(get_centroid, start, -1);
            dead[c] = true;
            for (const int u : g[c]) {
                if (dead[u]) continue;
                const int comp_sz = subtree_size[u];
                par_cr[u] = rec(u, comp_sz);
                subtree_size[u] = comp_sz;
            }

            const auto compare = [&](int i, int j) {
                return subtree_size[i] > subtree_size[j];
            };

            priority_queue<int, vector<int>, decltype(compare)> pq{compare};

            for (const int v : g[c]) {
                if (dead[v]) continue;
                link[v] = -1;
                pq.push(v);
            }

            const auto build_data_structure = [&](const int root_head, const int child_index) {
                queue<pair<int, int>> q;
                for (int root = root_head; root >= 0; root = link[root]) {
                    q.emplace(root, -1);
                }

                S x = 0;
                int idx = 0;
                int nxt = -1;
                while (!q.empty()) {
                    int cur = q.front().first;
                    int prev = q.front().second;
                    q.pop();
                    if (cur == nxt) {
                        d[idx++] = exchange(x, 0);
                        nxt = -1;
                    }

                    info[cur][dinfo[cur]++] = {child_index, idx};
                    x += leaf[cur];

                    for (const int v : g[cur]) {
                        if (v == prev or dead[v]) continue;
                        q.emplace(v, cur);
                        if (nxt == -1) nxt = v;
                    }
                }
                d[idx++] = x;
                return idx;
            };

            while (pq.size() >= 2) {
                const int p1 = pq.top();
                pq.pop();
                const int p2 = pq.top();
                pq.pop();

                if (pq.empty()) {
                    parent[par_cr[p1]] = parent[par_cr[p2]] = c;
                    ds_size[c][0] = build_data_structure(head[p1], 0);
                    subtrees[c][0] = fenwick_tree<S>(ds_size[c][0]);
                    for (int i = 0; i < ds_size[c][0]; i++) {
                        subtrees[c][0].add(i, d[i]);
                    }

                    ds_size[c][1] = build_data_structure(head[p2], 1);
                    subtrees[c][1] = fenwick_tree<S>(ds_size[c][1]);
                    for (int i = 0; i < ds_size[c][1]; i++) {
                        subtrees[c][1].add(i, d[i]);
                    }
                    break;
                }

                subtree_size[node_idx] = subtree_size[p1] + subtree_size[p2];
                par_cr[node_idx] = node_idx;

                parent[par_cr[p1]] = parent[par_cr[p2]] = node_idx;
                ds_size[node_idx][0] = build_data_structure(head[p1], 0);
                subtrees[node_idx][0] = fenwick_tree<S>(ds_size[node_idx][0]);
                for (int i = 0; i < ds_size[node_idx][0]; i++) {
                    subtrees[node_idx][0].add(i, d[i]);
                }
                ds_size[node_idx][1] = build_data_structure(head[p2], 1);
                subtrees[node_idx][1] = fenwick_tree<S>(ds_size[node_idx][1]);

                for (int i = 0; i < ds_size[node_idx][1]; i++) {
                    subtrees[node_idx][1].add(i, d[i]);
                }

                head[node_idx] = head[p1];
                tail[node_idx] = tail[p2];
                link[tail[p1]] = head[p2];
                pq.push(node_idx);
                node_idx++;
            }

            if (!pq.empty()) {
                int u = pq.top();
                pq.pop();
                parent[par_cr[u]] = c;
                ds_size[c][0] = build_data_structure(head[u], 0);
                subtrees[c][0] = fenwick_tree<S>(ds_size[c][0]);
                for (int i = 0; i < ds_size[c][0]; i++) {
                    subtrees[c][0].add(i, d[i]);
                }
            }

            dead[c] = false;
            return c;
        };

        rec(0, n);
        parent.resize(node_idx);
        parent.shrink_to_fit();
        subtrees.resize(node_idx);
        subtrees.shrink_to_fit();
    }

    void add(int p, S x) {
        p = ord[p];
        leaf[p] += x;
        int cur = parent[p];
        for (int i = 0; i < dinfo[p]; i++) {
            const auto &[b, dist] = info[p][i];
            subtrees[exchange(cur, parent[cur])][b].add(dist, x);
        }
    }

    S get(int p) {
        return leaf[ord[p]];
    }

    S prod(int p, int lower, int upper) {
        p = ord[p];
        S ret = 0;
        if (lower <= 0 and 0 < upper) {
            assert(0 <= p and p < n);
            ret = leaf[p];
        }
        ret += ds_prod(subtrees[p][0], ds_size[p][0], lower - 1, upper - 1);
        ret += ds_prod(subtrees[p][1], ds_size[p][1], lower - 1, upper - 1);
        int v = parent[p];
        for (int i = 0; i < dinfo[p]; i++) {
            const auto &[b, dist] = info[p][i];
            int ql = lower - dist - 1;
            int qr = upper - dist - 1;
            if (v < n and ql <= 0 and 0 < qr) ret += leaf[v];
            ret += ds_prod(subtrees[exchange(v, parent[v])][b ^ 1], ds_size[v][b ^ 1], ql - 1, qr - 1);
        }
        return ret;
    }
};
#line 6 "verify/LibraryChecker/tree/VertexAddRangeContourSumonTree.test.cpp"

using S = lint;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    in(n, q);
    vector<S> a(n);
    in(a);
    CentroidDecomposition<S> t(n);

    rep(i, n - 1) {
        int u, v;
        in(u, v);
        t.add_edge(u, v);
    }

    t.build(a);

    rep(i, q) {
        int com;
        in(com);
        if (com == 0) {
            int p;
            S x;
            in(p, x);
            t.add(p, x);
        } else {
            int p, l, r;
            in(p, l, r);
            out(t.prod(p, l, r));
        }
    }
}
Back to top page