#define PROBLEM "https://yukicoder.me/problems/no/1038" #include #include #include #include #include #include #include #include namespace suisen { template struct PointGetRangeContourOperate { using value_type = T; using operator_type = F; private: struct InternalCommutativeDualSegmentTree { InternalCommutativeDualSegmentTree(int n = 0) : _n(n), _laz(2 * _n, id()) {} void apply(int l, int r, const operator_type& f) { l = std::max(0, l), r = std::min(r, _n); for (l += _n, r += _n; l < r; l >>= 1, r >>= 1) { if (l & 1) _laz[l] = composition(f, _laz[l]), ++l; if (r & 1) --r, _laz[r] = composition(f, _laz[r]); } } operator_type get(int i) const { operator_type res = id(); for (i += _n; i; i >>= 1) res = composition(res, _laz[i]); return res; } private: int _n; std::vector _laz; }; using sequence_type = InternalCommutativeDualSegmentTree; struct AuxInfo { int8_t child_index; int dep; }; struct TreeNode { std::vector adj; typename std::array::iterator info_it; }; public: PointGetRangeContourOperate(int n = 0, const value_type& fill_v = {}) : PointGetRangeContourOperate(std::vector(n, fill_v)) {} PointGetRangeContourOperate(const std::vector& a) : _n(a.size()), _dat(a), _nodes(_n), _par(2 * _n, -1), _info(_n), _subtrees(2 * _n), _ord(_n, -1) {} void add_edge(int u, int v) { _nodes[u].adj.push_back(v); _nodes[v].adj.push_back(u); } // O(NlogN) void build() { std::mt19937 rng{ std::random_device{}() }; reorder(std::uniform_int_distribution{ 0, _n - 1 }(rng)); int new_node = _n; std::vector sub_size(2 * _n, 0); std::vector ctr(2 * _n, -1); std::vector head(2 * _n), tail(2 * _n), link(2 * _n); for (int i = 0; i < _n; ++i) head[i] = tail[i] = i; 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) { link[v] = -1; pq.push(v); } auto build_sequence = [&, this](const int root_head, const bool child_index) { std::deque> dq; for (int root = root_head; root >= 0; root = link[root]) dq.emplace_back(root, -1); int dep = 0, nxt = -1; while (dq.size()) { const auto [u, pu] = dq.front(); dq.pop_front(); if (u == nxt) ++dep, nxt = -1; auto& node = _nodes[u]; *node.info_it++ = { child_index, dep }; for (int v : node.adj) if (v != pu) { dq.emplace_back(v, u); if (nxt < 0) nxt = v; } } return sequence_type(++dep); }; 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(head[u], 0); _subtrees[c][1] = build_sequence(head[v], 1); break; } sub_size[new_node] = sub_size[u] + sub_size[v]; ctr[new_node] = new_node; _par[ctr[u]] = _par[ctr[v]] = new_node; _subtrees[new_node][0] = build_sequence(head[u], 0); _subtrees[new_node][1] = build_sequence(head[v], 1); head[new_node] = head[u], tail[new_node] = tail[v], link[tail[u]] = head[v]; pq.push(new_node); ++new_node; } if (pq.size()) { int u = pq.top(); pq.pop(); _par[ctr[u]] = c; _subtrees[c][0] = build_sequence(head[u], 0); } for (int v : _nodes[c].adj) _nodes[v].adj.push_back(c); return c; }; rec(rec, 0, _n); _par.resize(new_node), _par.shrink_to_fit(); _subtrees.resize(new_node), _subtrees.shrink_to_fit(); } // O((logN)^2) value_type get(int u) const { u = _ord[u]; 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 = mapping(_subtrees[std::exchange(v, _par[v])][it->child_index].get(it->dep), res); return res; } // O(1) void apply(int u, const operator_type& f) { u = _ord[u]; _dat[u] = mapping(f, _dat[u]); } // O((logN)^2) void apply(int u, int dl, int dr, const operator_type& f) { u = _ord[u]; if (dl <= 0 and 0 < dr) _dat[u] = mapping(f, _dat[u]); _subtrees[u][0].apply(dl - 1, dr - 1, f); _subtrees[u][1].apply(dl - 1, dr - 1, f); 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->dep - 1, qr = dr - it->dep - 1; if (v < _n and ql <= 0 and 0 < qr) _dat[v] = mapping(f, _dat[v]); _subtrees[std::exchange(v, _par[v])][it->child_index ^ 1].apply(ql - 1, qr - 1, f); } } private: int _n; std::vector _dat; std::vector _nodes; std::vector _par; std::vector> _info; std::vector> _subtrees; std::vector _ord; void reorder(int s) { _ord.assign(_n, -1); int t = 0; std::deque dq{ s }; while (dq.size()) { int u = dq.front(); dq.pop_front(); _ord[u] = t++; for (int v : _nodes[u].adj) if (_ord[v] < 0) dq.push_back(v); } assert(t == _n); std::vector tmp(_n); for (int i = 0; i < _n; ++i) { for (int& e : _nodes[i].adj) e = _ord[e]; _nodes[i].info_it = _info[_ord[i]].begin(); tmp[_ord[i]] = std::move(_nodes[i]); } _nodes.swap(tmp); } }; } // namespace suisen long long mapping(long long f, long long x) { return f + x; } long long composition(long long x, long long y) { return x + y; } long long id() { return 0; } #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; suisen::PointGetRangeContourOperate g(n, 0LL); for (int i = 0; i < n - 1; ++i) { int u, v; std::cin >> u >> v; --u, --v; g.add_edge(u, v); } std::vector> qs(q); for (auto &[x, y, z] : qs) { std::cin >> x >> y >> z; --x, ++y; } std::vector ans(q); auto t1 = std::chrono::system_clock::now(); g.build(); auto t2 = std::chrono::system_clock::now(); for (int i = 0; i < q; ++i) { const auto &[x, y, z] = qs[i]; ans[i] = g.get(x); g.apply(x, 0, y, z); } auto t3 = std::chrono::system_clock::now(); for (auto &e : ans) std::cout << e << '\n'; auto build_time_ms = std::chrono::duration_cast(t2 - t1).count(); auto query_time_ms = std::chrono::duration_cast(t3 - t2).count(); std::cerr << "build : " << build_time_ms << " ms" << std::endl; std::cerr << "query : " << query_time_ms << " ms" << std::endl; return 0; }