#include #include #include #include #include #include #include #include #include #include namespace suisen { namespace default_operator { template auto zero() -> decltype(T { 0 }) { return T { 0 }; } template auto one() -> decltype(T { 1 }) { return T { 1 }; } template auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; } template auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; } template auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; } template auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; } template auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; } template auto neg(const T &x) -> decltype(-x) { return -x; } template auto inv(const T &x) -> decltype(one() / x) { return one() / x; } } // default_operator namespace default_operator_noref { template auto zero() -> decltype(T { 0 }) { return T { 0 }; } template auto one() -> decltype(T { 1 }) { return T { 1 }; } template auto add(T x, T y) -> decltype(x + y) { return x + y; } template auto sub(T x, T y) -> decltype(x - y) { return x - y; } template auto mul(T x, T y) -> decltype(x * y) { return x * y; } template auto div(T x, T y) -> decltype(x / y) { return x / y; } template auto mod(T x, T y) -> decltype(x % y) { return x % y; } template auto neg(T x) -> decltype(-x) { return -x; } template auto inv(T x) -> decltype(one() / x) { return one() / x; } } // default_operator } // namespace suisen namespace suisen { template , T(*_zero)() = default_operator_noref::zero, T(*_neg)(T) = default_operator_noref::neg> struct PointGetRangeContourAddOnTree { using value_type = T; private: struct InternalFenwickTree { InternalFenwickTree() = default; InternalFenwickTree(int n) : _n(n), _dat(_n + 1, _zero()) {} value_type get(int i) const { value_type res = _zero(); for (++i; i; i -= i & -i) res = _add(res, _dat[i]); return res; } void add(int l, int r, const value_type& val) { l = std::max(0, l), r = std::min(r, _n); if (l < r) add(l, val), add(r, _neg(val)); } private: int _n; std::vector _dat; void add(int r, const value_type& val) { for (++r; r <= _n; r += r & -r) _dat[r] = _add(_dat[r], val); } }; using sequence_type = InternalFenwickTree; struct AuxInfo { int8_t child_index; int dist; }; struct TreeNode { std::vector adj; typename std::array::iterator info_it; }; public: PointGetRangeContourAddOnTree(int n = 0, const value_type& fill_value = _zero()) : PointGetRangeContourAddOnTree(std::vector(n, fill_value)) {} PointGetRangeContourAddOnTree(const std::vector& dat) : _n(dat.size()), _dat(dat), _nodes(_n), _par(_n, -1), _info(_n), _subtrees(_n) { _par.reserve(2 * _n); _subtrees.reserve(2 * _n); for (int i = 0; i < _n; ++i) { _nodes[i].info_it = _info[i].begin(); } } void add_edge(int u, int v) { _nodes[u].adj.push_back(v); _nodes[v].adj.push_back(u); } void build() { std::vector sub_size(_n, 0); std::vector ctr(_n, -1); sub_size.reserve(2 * _n); ctr.reserve(2 * _n); std::vector> ch(_n); ch.reserve(2 * _n); auto merge = [&](std::vector&& l, std::vector&& r) -> std::vector&& { if (l.size() > r.size()) std::swap(l, r); for (int v : l) r.push_back(v); return std::move(r); }; auto rec = [&](auto rec, int r, int siz) -> int { int c = -1; auto get_centroid = [&](auto get_centroid, int u, int p) -> void { sub_size[u] = 1; for (int v : _nodes[u].adj) if (v != p) { get_centroid(get_centroid, v, u); if (v == c) { sub_size[u] = siz - sub_size[c]; break; } sub_size[u] += sub_size[v]; } if (c < 0 and sub_size[u] * 2 > siz) c = u; }; get_centroid(get_centroid, r, -1); for (int v : _nodes[c].adj) { const int comp_size = sub_size[v]; _nodes[v].adj.erase(std::find(_nodes[v].adj.begin(), _nodes[v].adj.end(), c)); ctr[v] = rec(rec, v, comp_size); sub_size[v] = comp_size; } auto comp = [&](int i, int j) { return sub_size[i] > sub_size[j]; }; std::priority_queue, decltype(comp)> pq{ comp }; for (int v : _nodes[c].adj) { ch[v] = { v }; pq.push(v); } auto build_sequence = [this](const std::vector& roots, const bool child_index) { std::deque> dq; for (int r : roots) dq.emplace_back(r, -1); int dist = -1, nxt = roots.front(); while (dq.size()) { const auto [u, pu] = dq.front(); dq.pop_front(); if (u == nxt) ++dist, nxt = -1; auto& node = _nodes[u]; *node.info_it++ = { child_index, dist }; for (int v : node.adj) if (v != pu) { dq.emplace_back(v, u); if (nxt < 0) nxt = v; } } return sequence_type(dist + 1); }; while (pq.size() >= 2) { const int u = pq.top(); pq.pop(); const int v = pq.top(); pq.pop(); if (pq.empty()) { _par[ctr[u]] = _par[ctr[v]] = c; _subtrees[c][0] = build_sequence(ch[u], 0); _subtrees[c][1] = build_sequence(ch[v], 1); break; } const int new_node = sub_size.size(); sub_size.push_back(sub_size[u] + sub_size[v]); ctr.push_back(new_node); _par.push_back(-1); _par[ctr[u]] = _par[ctr[v]] = new_node; _subtrees.emplace_back(); _subtrees[new_node][0] = build_sequence(ch[u], 0); _subtrees[new_node][1] = build_sequence(ch[v], 1); ch.push_back(merge(std::move(ch[u]), std::move(ch[v]))); ch[u].clear(), ch[u].shrink_to_fit(); ch[v].clear(), ch[v].shrink_to_fit(); pq.push(new_node); } if (pq.size()) { int u = pq.top(); pq.pop(); _par[ctr[u]] = c; _subtrees[c][0] = build_sequence(ch[u], 0); } for (int v : _nodes[c].adj) _nodes[v].adj.push_back(c); return c; }; rec(rec, 0, _n); } value_type get(int u) const { value_type res = _dat[u]; int v = _par[u]; const auto it_end = _nodes[u].info_it; for (auto it = _info[u].begin(); it != it_end; ++it) { res = _add(res, _subtrees[std::exchange(v, _par[v])][it->child_index].get(it->dist)); } return res; } void set(int u, const value_type& new_val) { add(u, _add(new_val, _neg(get(u)))); } void add(int u, const value_type &val) { _nodes[u].dat = _add(_dat[u], val); } void add(int u, int dl, int dr, const value_type &val) { if (dl <= 0 and 0 < dr) _dat[u] = _add(_dat[u], val); _subtrees[u][0].add(dl - 1, dr - 1, val); _subtrees[u][1].add(dl - 1, dr - 1, val); int v = _par[u]; const auto it_end = _nodes[u].info_it; for (auto it = _info[u].begin(); it != it_end; ++it) { int ql = dl - it->dist - 2, qr = dr - it->dist - 2; if (v < _n and ql <= -1 and -1 < qr) _dat[v] = _add(_dat[v], val); _subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].add(ql, qr, val); } } private: int _n; std::vector _dat; std::vector _nodes; std::vector _par; std::vector> _info; std::vector> _subtrees; }; } // namespace suisen int main() { auto beg_time = std::chrono::system_clock::now(); std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; suisen::PointGetRangeContourAddOnTree g(n); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; --u, --v; g.add_edge(u, v); } g.build(); auto mid_time = std::chrono::system_clock::now(); std::cerr << "build time : " << std::chrono::duration_cast(mid_time - beg_time).count() << std::endl; for (int i = 0; i < q; ++i) { int x, y, z; std::cin >> x >> y >> z; --x, ++y; std::cout << g.get(x) << '\n'; g.add(x, 0, y, z); } auto end_time = std::chrono::system_clock::now(); std::cerr << "query time : " << std::chrono::duration_cast(end_time - mid_time).count() << std::endl; return 0; }