#define PROBLEM "https://yukicoder.me/problems/no/1038" #include #include #include #include #include template struct CommutativeDualSegmentTree { CommutativeDualSegmentTree() {} CommutativeDualSegmentTree(int n) : _n(n) , _laz(2 * _n, e()) {} void apply(int l, int r, const T &f) { for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) { if (l & 1) _laz[l] = op(_laz[l], f), ++l; if (r & 1) --r, _laz[r] = op(_laz[r], f); } } T get(int i) { T res = e(); for (i += _n; i; i >>= 1) res = op(res, _laz[i]); return res; } private: int _n; std::vector _laz; }; template struct RangeContourOperationQueryOnTree { RangeContourOperationQueryOnTree() {} RangeContourOperationQueryOnTree(int n) : _n(n), _g(_n), _par(_n, -1), _removed(_n, false), _pos(_n), _idx(_n), _dist(_n), _sub(_n), _dat(_n, e()) {} using segtree_type = CommutativeDualSegmentTree; struct SubTree { std::vector _sep; segtree_type _seq; SubTree() {} SubTree( const std::vector>& g, const std::vector& removed, const int root, const bool is_right_child, std::vector>& idx, std::vector>& pos, std::vector>& dist ) { const int siz = dist.size(); auto is_dummy_vertex = [&](int u) { return u >= siz; }; _sep.push_back(0); std::deque> dq{ { root, -1, 0 } }; int pre_dist = 0, cnt = 0; while (dq.size()) { const auto [u, pu, du] = dq.front(); dq.pop_front(); if (du == pre_dist + 1) { _sep.push_back(cnt); pre_dist = du; } bool b = is_dummy_vertex(u); if (not b) { pos[u].push_back(cnt++); idx[u].push_back(is_right_child); dist[u].push_back(du); } for (int v : g[u]) { if (v == pu or removed[v]) continue; if (b) { dq.emplace_front(v, u, du); } else { dq.emplace_back(v, u, du + 1); } } } _sep.push_back(cnt); _seq = segtree_type(cnt); } T get(int i) { return _seq.get(i); } void apply(int dl, int dr, const T &val) { if (dl < 0) dl = 0; if (dr >= int(_sep.size())) dr = int(_sep.size()) - 1; if (dl >= dr) return; int ql = _sep[dl], qr = _sep[dr]; _seq.apply(ql, qr, val); } }; void add_edge(int u, int v) { _g[u].push_back(v); _g[v].push_back(u); } void build() { std::vector sub(_n, 0); std::vector ctr(_n, -1); auto rec = [&](auto rec, int r, int siz) -> int { int c = -1; auto get_centroid = [&](auto get_centroid, int u, int p) -> void { sub[u] = 1; for (int v : _g[u]) { if (v == p or _removed[v]) continue; get_centroid(get_centroid, v, u); if (v == c) { sub[u] = siz - sub[c]; break; } sub[u] += sub[v]; } if (c < 0 and sub[u] * 2 > siz) c = u; }; get_centroid(get_centroid, r, -1); _removed[c] = true; for (int v : _g[c]) { if (_removed[v]) continue; const int comp_size = sub[v]; ctr[v] = rec(rec, v, comp_size); sub[v] = comp_size; } auto comp = [&](int i, int j) { return sub[i] > sub[j]; }; std::priority_queue, decltype(comp)> pq{ comp }; for (int v : _g[c]) { if (_removed[v]) continue; pq.push(v); } while (pq.size() >= 2) { int u = pq.top(); pq.pop(); int v = pq.top(); pq.pop(); if (pq.empty()) { _par[ctr[u]] = _par[ctr[v]] = c; _sub[c][0] = SubTree{ _g, _removed, u, 0, _idx, _pos, _dist }; _sub[c][1] = SubTree{ _g, _removed, v, 1, _idx, _pos, _dist }; } else { int new_node = sub.size(); sub.push_back(sub[u] + sub[v]); ctr.push_back(new_node); _par.push_back(-1); _par[ctr[u]] = _par[ctr[v]] = new_node; pq.push(new_node); _removed.push_back(false); _g.emplace_back(); _g[new_node].push_back(u); _g[new_node].push_back(v); _sub.emplace_back(); _sub[new_node][0] = SubTree{ _g, _removed, u, 0, _idx, _pos, _dist }; _sub[new_node][1] = SubTree{ _g, _removed, v, 1, _idx, _pos, _dist }; } } if (pq.size()) { int u = pq.top(); pq.pop(); _par[ctr[u]] = c; _sub[c][0] = SubTree{ _g, _removed, u, 0, _idx, _pos, _dist }; } _removed[c] = false; return c; }; rec(rec, 0, _n); } T get(int u) { T res = _dat[u]; int h = _pos[u].size(); for (int i = 0, v = _par[u]; i < h; ++i) { res = op(res, _sub[std::exchange(v, _par[v])][_idx[u][i]].get(_pos[u][i])); } return res; } void apply(int u, int dl, int dr, const T &val) { if (dl <= 0 and 0 < dr) _dat[u] = op(_dat[u], val); _sub[u][0].apply(dl - 1, dr - 1, val); _sub[u][1].apply(dl - 1, dr - 1, val); int h = _pos[u].size(); for (int i = 0, v = _par[u]; i < h; ++i) { int ql = dl - _dist[u][i] - 2, qr = dr - _dist[u][i] - 2; if (v < _n and ql <= -1 and -1 < qr) _dat[v] = op(_dat[v], val); _sub[std::exchange(v, _par[v])][_idx[u][i] ^ 1].apply(ql, qr, val); } } private: int _n; std::vector> _g; std::vector _par; std::vector _removed; std::vector> _pos; std::vector> _idx; std::vector> _dist; std::vector> _sub; std::vector _dat; }; long long op(long long x, long long y) { return x + y; } long long e() { return 0; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; RangeContourOperationQueryOnTree 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(); 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.apply(x, 0, y, z); } return 0; }