verify/library_checker-vertex_add_path_sum.cpp

• View this file on GitHub
• Last update: 2026-05-31 15:33:44+09:00
• Problem: https://judge.yosupo.jp/problem/vertex_add_path_sum

Depends on

• templates/alias.hpp
• templates/macro.hpp
• HeavyLightDecomposition (tree/heavy_light_decomposition.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"

#include <bits/stdc++.h>
using namespace std;

#include "templates/alias.hpp"
#include "templates/macro.hpp"

#include "tree/heavy_light_decomposition.hpp"

int main() {
  ll N, Q;
  in(N, Q);
  vi A(N);
  in(A);

  vvi G(N);

  rep(_, N - 1) {
    ll u, v;
    in(u, v);

    G[u].emplace_back(v), G[v].emplace_back(u);
  }

  HeavyLightDecomposition<ll> hld(G);

  auto e = [&]() { return 0; };
  auto op = [](ll a, ll b) { return a + b; };

  vi seg(N * 2, e());

  rep(i, N) seg[hld.in[i] + N] = A[i];
  rrep(i, 1, N) { seg[i] = op(seg[i << 1], seg[i << 1 | 1]); }

  auto prod = [&](ll l, ll r) {
    // out(l, r);
    ll res = e();

    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        res = op(res, seg[l++]);
      if (r & 1)
        res = op(res, seg[--r]);
    }
    // out(res);

    return res;
  };
  auto seg_set = [&](ll x, ll a) {
    x += N;
    seg[x] += a;

    while (x >>= 1) {
      seg[x] = op(seg[x << 1], seg[x << 1 | 1]);
    }
  };

  while (Q--) {
    ll t;
    in(t);

    if (t == 0) {
      ll p, x;
      in(p, x);

      seg_set(hld.in[p], x);
    } else {
      ll u, v;
      in(u, v);

      out(hld.query<ll>(u, v, e, prod, op));
    }
  }
}

#line 1 "verify/library_checker-vertex_add_path_sum.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/vertex_add_path_sum"

#include <bits/stdc++.h>
using namespace std;

#line 7 "templates/alias.hpp"

template <class T> using VC = std::vector<T>;
template <class T>
using rpriority_queue = std::priority_queue<T, VC<T>, std::greater<T>>;
using ll = long long;
using ld = long double;
using pii = std::pair<ll, ll>;
using vi = VC<ll>;
using vvi = VC<vi>;
using vvvi = VC<vvi>;
using vb = VC<bool>;
using vvb = VC<vb>;
using vf = VC<double>;
using vvf = VC<vf>;
using vpii = VC<pii>;
using vvpii = VC<vpii>;
using si = std::set<ll>;
using spii = std::set<pii>;
using mii = std::map<ll, ll>;
const std::string upperlist = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const std::string lowerlist = "abcdefghijklmnopqrstuvwxyz";
#define mp make_pair
#define dms << " " <<

constexpr int MOD998 = 998244353;
#line 4 "templates/macro.hpp"

// 引数の長さで内容が変わるrep 参考: https://trap.jp/post/1224
#define overload4(a, b, c, d, ...) d
#define _rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, REP, _rep)(__VA_ARGS__)
#define _rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define RREP(i, a, b) for (int i = (int)(b - 1); i >= (int)(a); i--)
#define rrep(...) overload4(__VA_ARGS__, RREP, _rrep)(__VA_ARGS__)

#define all(a) (a).begin(), (a).end()

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

template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
  is >> p.first >> p.second;
  return is;
}

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

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

// pythonのprintライクな関数 参考:
// https://nyaannyaan.github.io/library/template/inout.hpp
inline void out() { std::cout << std::endl; }
template <typename T, typename... U, char sep = ' '>
void out(const T &t, const U &...u) {
  std::cout << t;

  if (sizeof...(u))
    std::cout << sep;

  out(u...);
}

// cinの短縮関数 参考: https://nyaannyaan.github.io/library/template/inout.hpp
inline void in() {}
template <typename T, class... U> void in(T &t, U &...u) {
  std::cin >> t;
  in(u...);
}

template <typename T> inline T ceil_div(T a, T b) { return (a + b - 1) / b; }
template <typename T> inline T mod_pow(T a, T n, T mod) {
  T res = 1;
  while (n) {
    if (n % 2 != 0) {
      res *= a;
      res %= mod;
    }

    a *= a;
    a %= mod;

    n >>= 1;
  }

  return res;
}
template <typename T> inline T minus_mod(T a, T b) { return ((a % b) + b) % b; }

template <typename T> void apply_vec(std::vector<T> &v, T (*fn)(T)) {
  for (int i = 0; i < v.size(); i++)
    v[i] = fn(v[i]);
}
#line 8 "verify/library_checker-vertex_add_path_sum.cpp"

#line 3 "tree/heavy_light_decomposition.hpp"

template <std::integral T> struct HeavyLightDecomposition {
public:
  std::vector<std::vector<T>> G;
  T n;
  std::vector<T> size, par, in, out, head, depth, rev;

  HeavyLightDecomposition(std::vector<std::vector<T>> G, T root = 0)
      : G{G}, n(static_cast<T>(G.size())), size(n, 0), par(n, -1), in(n, 0),
        out(n, 0), head(n, root), depth(n, 0), rev(n, -1), d{0}, o{0} {

    dfs_sz(root);
    dfs_hld(root);
  }

  T lca(T u, T v) {
    assert(0 <= u && u < n && 0 <= v && v < n);

    for (;; u = par[head[u]]) {
      if (in[u] < in[v])
        std::swap(u, v);

      if (head[u] == head[v])
        return v;
    }
  }

  template <typename S>
  S query(T u, T v, const auto &e, const auto &q, const auto &op,
          bool edge = false) {
    assert(0 <= u && u < n && 0 <= v && v < n);

    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(std::is_convertible_v<decltype(q), std::function<S(T, T)>>,
                  "q must work as S(T, T)");

    S l = e(), r = e();

    for (;; u = par[head[u]]) {
      if (in[u] < in[v])
        std::swap(u, v), std::swap(l, r);
      if (head[u] == head[v])
        break;

      l = op(q(in[head[u]], in[u] + 1), l);
    }

    return op(op(q(in[v] + edge, in[u] + 1), l), r);
  }

private:
  T d, o;

  void dfs_sz(T cur) {
    size[cur] = 1;

    if (G[cur].size() >= 2 && G[cur][0] == par[cur])
      swap(G[cur][0], G[cur][1]);

    for (auto &nxt : G[cur]) {
      if (par[cur] == nxt)
        continue;

      par[nxt] = cur;
      dfs_sz(nxt);
      size[cur] += size[nxt];

      if (size[G[cur][0]] < size[nxt])
        swap(G[cur][0], nxt);
    }
  }

  void dfs_hld(T cur) {
    in[cur] = o++, rev[in[cur]] = cur;
    depth[cur] = d;

    for (auto nxt : G[cur]) {
      if (nxt == par[cur])
        continue;

      head[nxt] = (nxt == G[cur][0] ? head[cur] : nxt);
      ++d, dfs_hld(nxt), --d;
    }

    out[cur] = o;
  }
};

/**
 * @file tree/heavy_light_decomposition.hpp
 * @brief HeavyLightDecomposition
 * @auther hidehic0
 * @date 2026-05-31
 */
#line 10 "verify/library_checker-vertex_add_path_sum.cpp"

int main() {
  ll N, Q;
  in(N, Q);
  vi A(N);
  in(A);

  vvi G(N);

  rep(_, N - 1) {
    ll u, v;
    in(u, v);

    G[u].emplace_back(v), G[v].emplace_back(u);
  }

  HeavyLightDecomposition<ll> hld(G);

  auto e = [&]() { return 0; };
  auto op = [](ll a, ll b) { return a + b; };

  vi seg(N * 2, e());

  rep(i, N) seg[hld.in[i] + N] = A[i];
  rrep(i, 1, N) { seg[i] = op(seg[i << 1], seg[i << 1 | 1]); }

  auto prod = [&](ll l, ll r) {
    // out(l, r);
    ll res = e();

    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        res = op(res, seg[l++]);
      if (r & 1)
        res = op(res, seg[--r]);
    }
    // out(res);

    return res;
  };
  auto seg_set = [&](ll x, ll a) {
    x += N;
    seg[x] += a;

    while (x >>= 1) {
      seg[x] = op(seg[x << 1], seg[x << 1 | 1]);
    }
  };

  while (Q--) {
    ll t;
    in(t);

    if (t == 0) {
      ll p, x;
      in(p, x);

      seg_set(hld.in[p], x);
    } else {
      ll u, v;
      in(u, v);

      out(hld.query<ll>(u, v, e, prod, op));
    }
  }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost_line_00	AC	1534 ms	138 MB
g++	almost_line_01	AC	1700 ms	135 MB
g++	example_00	AC	2 ms	3 MB
g++	line_00	AC	1377 ms	133 MB
g++	line_01	AC	1461 ms	141 MB
g++	long-path-decomposition_killer_00	AC	934 ms	117 MB
g++	max_random_00	AC	1671 ms	122 MB
g++	max_random_01	AC	1572 ms	122 MB
g++	max_random_02	AC	1560 ms	122 MB
g++	random_00	AC	1207 ms	96 MB
g++	random_01	AC	1450 ms	113 MB
g++	random_02	AC	631 ms	16 MB
g++	random_03	AC	660 ms	105 MB
g++	random_04	AC	613 ms	69 MB
g++	small_00	AC	3 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	3 ms	3 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	4 ms	4 MB

Back to top page