#line 1 "Main.cpp" #include #line 2 "nachia\\tree\\centroid-decomposition-binary-tree.hpp" #line 2 "nachia\\graph\\adjacency-list.hpp" #include #include namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyList(int n, const std::vector>& edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = v; if(rev) E[--buf[v]] = u; } I = std::move(buf); } AdjacencyList(const std::vector>& edges = {}){ int n = mn = edges.size(); std::vector buf(n+1, 0); for(int i=0; i targets, std::vector bounds){ AdjacencyList res; res.mn = bounds.size() - 1; res.E = std::move(targets); res.I = std::move(bounds); return res; } AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyList reversed_edges() const { AdjacencyList res; int n = res.mn = mn; std::vector buf(n+1, 0); for(int v : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u #line 8 "nachia\\tree\\centroid-decomposition-binary-tree.hpp" #include #include namespace nachia { struct CentroidDecompositionBinaryTree{ private: struct VectorIntView{ using Iter = typename std::vector::iterator; Iter li, ri; VectorIntView(std::vector& src, int l, int r) : li(src.begin() + l) , ri(src.begin() + r) {} Iter begin() const { return li; } Iter end() const { return ri; } int size() const { return ri - li; } int& operator[](int i) const { return li[i]; } }; struct CDBTNode{ int array_idx; int cd_depth; int sib; int parent; int array_left; int size; int exclude_cent; }; struct UpdatePoint { int i; int p; }; struct QueryRange { int i, l, r; }; std::vector> cd_dist; std::vector bt_nodes; std::vector> bt_arrays; std::vector> bt_arrays_sep; std::vector> update_points; QueryRange get_one_node_range(const CDBTNode& node, int l, int r){ QueryRange res; res.i = node.array_idx; res.l = bt_arrays_sep[res.i][node.array_left + std::max(0, std::min(l - node.exclude_cent, node.size))]; res.r = bt_arrays_sep[res.i][node.array_left + std::max(0, std::min(r - node.exclude_cent, node.size))]; return res; } VectorIntView array_for_node(std::vector>& src, const CDBTNode& node){ return VectorIntView(src[node.array_idx], node.array_left, node.array_left + node.size); } VectorIntView sep_for_node(std::vector>& src, const CDBTNode& node){ return VectorIntView(src[node.array_idx], node.array_left, node.array_left + (node.size + 1)); } static int find_centroid( const nachia::AdjacencyList& adj, std::vector& Z, int root ){ while(true){ int nx = -1; for(int c : adj[root]) if(Z[c] * 2 > Z[root]){ nx = c; break; } if(nx < 0) break; Z[root] -= Z[nx]; Z[nx] += Z[root]; root = nx; } return root; } public: CentroidDecompositionBinaryTree() {} CentroidDecompositionBinaryTree(const nachia::AdjacencyList& adj){ int n = adj.num_vertices(); assert(1 <= n); std::vector Z; { std::vector bfs = {0}; std::vector P(n,-1); for(int i=0; i=1; i--) Z[P[bfs[i]]] += Z[bfs[i]]; } std::vector> cd_bfs; std::vector cd_bfs_adji = { 1 }; std::vector cd_dep(n, -1); std::vector cd_component_size(n); cd_bfs.push_back(std::make_pair(-1, find_centroid(adj, Z, 0))); cd_dep[cd_bfs.front().second] = 0; for(int i=0; i<(int)cd_bfs.size(); i++){ int g = cd_bfs[i].second; cd_component_size[g] = Z[g]; Z[g] = 0; for(int nx : adj[g]) if(cd_dep[nx] == -1){ int nxg = find_centroid(adj, Z, nx); cd_bfs.push_back(std::make_pair(nx, nxg)); cd_dep[nxg] = cd_dep[g] + 1; } cd_bfs_adji.push_back(cd_bfs.size()); } int cd_height = *std::max_element(cd_dep.begin(), cd_dep.end()); cd_dist.assign(cd_height+1, std::vector(n, -1)); for(int dep=0; dep<=cd_height; dep++){ std::vector bfs; for(int s=0; s dep) if(cd_dist[dep][e] == -1){ bfs.push_back(e); cd_dist[dep][e] = cd_dist[dep][p] + 1; } } } bt_nodes.resize(n*2-1); for(auto& v : bt_nodes) v.sib = v.array_idx = v.parent = -1; { std::vector cdbt_root_id(n); for(int i=0; i> bt_children(n*2-1); for(int i=0; i> Que; // ( -size, root ) for(int ii=n-1; ii>=0; ii--){ auto [nx,g] = cd_bfs[ii]; Que.push(std::make_pair(-1, g)); for(int ei=cd_bfs_adji[ii]; ei= 2){ auto a = Que.top().second; Que.pop(); auto b = Que.top().second; Que.pop(); int idx = cdbt_node_count; bt_nodes[a].sib = b; bt_nodes[b].sib = a; bt_nodes[a].parent = idx; bt_nodes[b].parent = idx; bt_nodes[idx].cd_depth = cd_dep[g]; bt_nodes[idx].size = bt_nodes[a].size + bt_nodes[b].size; bt_nodes[idx].exclude_cent = bt_nodes[a].exclude_cent & bt_nodes[b].exclude_cent; bt_children[idx] = std::make_pair(a,b); Que.push(std::make_pair(-bt_nodes[idx].size, idx)); cdbt_node_count++; } auto r = Que.top().second; Que.pop(); bt_nodes[r].cd_depth--; cdbt_root_id[g] = r; bt_nodes[r].exclude_cent = 1; } bt_nodes.back().array_idx = -1; std::vector arraysz; for(int idx=n*2-2; idx>=n; idx--){ auto [a,b] = bt_children[idx]; int array_idx = bt_nodes[idx].array_idx + 1; if((int)arraysz.size() == array_idx) arraysz.push_back(0); bt_nodes[a].array_idx = array_idx; bt_nodes[a].array_left = arraysz[array_idx]; arraysz[array_idx] += bt_nodes[a].size; bt_nodes[b].array_idx = array_idx; bt_nodes[b].array_left = arraysz[array_idx]; arraysz[array_idx] += bt_nodes[b].size; } bt_arrays.resize(arraysz.size()); for(int i=0; i<(int)arraysz.size(); i++) bt_arrays[i].resize(arraysz[i]); bt_arrays_sep.resize(arraysz.size()); for(int i=0; i<(int)arraysz.size(); i++) bt_arrays_sep[i].resize(arraysz[i] + 1); for(int idx=0; idx sep_buf(n+1, 0); for(int idx=n; idx<2*n-1; idx++) if(bt_nodes[idx].parent >= 0){ auto& node = bt_nodes[idx]; auto [a,b] = bt_children[idx]; int dep = node.cd_depth; auto array_view = array_for_node(bt_arrays, node); auto sep_view = sep_for_node(bt_arrays_sep, node); int ex = node.exclude_cent; for(int i=0; i<=node.size; i++) sep_buf[i] = 0; for(int p : array_for_node(bt_arrays, bt_nodes[a])) sep_buf[cd_dist[dep][p] - ex]++; for(int p : array_for_node(bt_arrays, bt_nodes[b])) sep_buf[cd_dist[dep][p] - ex]++; for(int i=0; i& get_array(int id) const { return bt_arrays[id]; } const std::vector get_update_points(int vtx) const { return update_points[vtx]; } std::vector get_query_range(int from, int distl, int distr){ int p = from; std::vector res; if(distl <= 0 && 0 < distr){ res.push_back({ bt_nodes[p].array_idx, bt_nodes[p].array_left, bt_nodes[p].array_left + 1 }); } while(bt_nodes[p].parent != -1){ auto& sibnode = bt_nodes[bt_nodes[p].sib]; int d = cd_dist[sibnode.cd_depth][from]; auto tmp = get_one_node_range(sibnode, distl-d, distr-d); if(tmp.l < tmp.r) res.push_back(tmp); p = bt_nodes[p].parent; } return res; } }; } // namespace nachia #line 4 "Main.cpp" #include int main() { //nachia::InputBufIterator iitr; //nachia::OutputBufIterator oitr; std::cin.tie(nullptr)->sync_with_stdio(false); int N; std::cin >> N; int Q; std::cin >> Q; std::vector> edges(N-1); for(auto& e : edges){ int u; std::cin >> u; u--; int v; std::cin >> v; v--; e = { u, v }; } nachia::CentroidDecompositionBinaryTree tree(nachia::AdjacencyList(N, edges, true)); std::vector> rq(tree.get_array_count()); for(int i=0; i(arr.size()+1); } for(int i=0; i> x; x--; int y; std::cin >> y; int z; std::cin >> z; long long ans = 0; for(auto q : tree.get_update_points(x)){ ans += rq[q.i].sum(0, q.p+1); } std::cout << ans << '\n'; for(auto q : tree.get_query_range(x, 0, y+1)){ rq[q.i].add(q.l, z); rq[q.i].add(q.r, -z); } } return 0; }