#line 2 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\array\\csr-array.hpp" #include #include #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ 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 Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 4 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" #include #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\graph\\graph.hpp" namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } }; using Base = std::vector>; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i static Graph Input(Cin& cin, int n, bool undirected, int m, bool offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } int numVertices() const noexcept { return m_n; } int numEdges() const noexcept { return int(m_e.size()); } int addNode() noexcept { return m_n++; } int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; } Edge& operator[](int ei) noexcept { return m_e[ei]; } const Edge& operator[](int ei) const noexcept { return m_e[ei]; } Edge& at(int ei) { return m_e.at(ei); } const Edge& at(int ei) const { return m_e.at(ei); } auto begin(){ return m_e.begin(); } auto end(){ return m_e.end(); } auto begin() const { return m_e.begin(); } auto end() const { return m_e.end(); } bool isUndirected() const noexcept { return m_isUndir; } void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); } void contract(int newV, const std::vector& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = newV[mapping[i]]++; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(auto e : m_e){ src.emplace_back(e.from, e.to); if(undirected) src.emplace_back(e.to, e.from); } return CsrArray::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia #line 6 "D:\\Programming\\VSCode\\competitive-cpp\\nachia\\tree\\heavy-light-decomposition.hpp" namespace nachia{ struct HeavyLightDecomposition{ private: int N; std::vector P; std::vector PP; std::vector PD; std::vector D; std::vector I; std::vector rangeL; std::vector rangeR; public: HeavyLightDecomposition(const CsrArray& E = CsrArray::Construct(1, {}), int root = 0){ N = E.size(); P.assign(N, -1); I = {root}; I.reserve(N); for(int i=0; i<(int)I.size(); i++){ int p = I[i]; for(int e : E[p]) if(P[p] != e){ I.push_back(e); P[e] = p; } } std::vector Z(N, 1); std::vector nx(N, -1); PP.resize(N); for(int i=0; i=1; i--){ int p = I[i]; Z[P[p]] += Z[p]; if(nx[P[p]] == -1) nx[P[p]] = p; if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p; } for(int p : I) if(nx[p] != -1) PP[nx[p]] = p; PD.assign(N,N); PD[root] = 0; D.assign(N,0); for(int p : I) if(p != root){ PP[p] = PP[PP[p]]; PD[p] = std::min(PD[PP[p]], PD[P[p]]+1); D[p] = D[P[p]]+1; } rangeL.assign(N,0); rangeR.assign(N,0); for(int p : I){ rangeR[p] = rangeL[p] + Z[p]; int ir = rangeR[p]; for(int e : E[p]) if(P[p] != e) if(e != nx[p]){ rangeL[e] = (ir -= Z[e]); } if(nx[p] != -1){ rangeL[nx[p]] = rangeL[p] + 1; } } I.resize(N); for(int i=0; i PD[v]) u = P[PP[u]]; while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; } return (D[u] > D[v]) ? v : u; } int dist(int u, int v) const { return depth(u) + depth(v) - depth(lca(u,v)) * 2; } std::vector> path(int r, int c, bool include_root = true, bool reverse_path = false) const { if(PD[c] < PD[r]) return {}; std::vector> res(PD[c]-PD[r]+1); for(int i=0; i<(int)res.size()-1; i++){ res[i] = std::make_pair(rangeL[PP[c]], rangeL[c]+1); c = P[PP[c]]; } if(PP[r] != PP[c] || D[r] > D[c]) return {}; res.back() = std::make_pair(rangeL[r]+(include_root?0:1), rangeL[c]+1); if(res.back().first == res.back().second) res.pop_back(); if(!reverse_path) std::reverse(res.begin(),res.end()); else for(auto& a : res) a = std::make_pair(N - a.second, N - a.first); return res; } std::pair subtree(int p){ return std::make_pair(rangeL[p], rangeR[p]); } int median(int x, int y, int z) const { return lca(x,y) ^ lca(y,z) ^ lca(x,z); } int la(int from, int to, int d) const { if(d < 0) return -1; int g = lca(from,to); int dist0 = D[from] - D[g] * 2 + D[to]; if(dist0 < d) return -1; int p = from; if(D[from] - D[g] < d){ p = to; d = dist0 - d; } while(D[p] - D[PP[p]] < d){ d -= D[p] - D[PP[p]] + 1; p = P[PP[p]]; } return I[rangeL[p] - d]; } }; } // namespace nachia #line 2 "..\\Main.cpp" #include #include #line 7 "..\\Main.cpp" #include #include #include using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; using Val = i64; struct SegtreeNode { i64 mingap; i64 leftdiff; }; SegtreeNode segtree_op(SegtreeNode l, SegtreeNode r){ return { min(l.mingap - r.leftdiff, r.mingap), l.leftdiff + r.leftdiff }; } SegtreeNode segtree_e(){ return { INF, 0 }; } int main(){ int N, Q; cin >> N >> Q; auto tree = nachia::Graph(N, true); auto hld = nachia::HeavyLightDecomposition(); vector W(N); { vector C(N-1); rep(i,N-1){ int u,v; cin >> u >> v >> C[i]; u--; v--; tree.addEdge(u, v); } hld = nachia::HeavyLightDecomposition(tree); rep(i,N-1){ if(hld.parentOf(tree[i].to) != tree[i].from) tree[i].reverse(); W[hld.toSeq(tree[i].to)] = C[i]; } } using Segtree = atcoder::segtree; atcoder::dsu dsu(N); vector dsu_most_left(N); rep(i,N) dsu_most_left[i] = i; Segtree segtree(N+1); int ans = N; auto add_diff = [&](int pos, i64 val){ auto buf = segtree.get(pos); segtree.set(pos, { buf.mingap, buf.leftdiff + val }); }; vector gapsum(N); auto clear_range = [&](int l, int r){ int p = dsu_most_left[dsu.leader(r-1)]; while(l <= p){ auto buf = segtree.get(p); segtree.set(p, { INF, buf.leftdiff }); int v = hld.toVtx(p); for(auto path : hld.path(0, v)){ add_diff(path.first, gapsum[v]); add_diff(path.second, -gapsum[v]); } gapsum[v] = 0; int nx = dsu_most_left[dsu.leader(p-1)]; dsu_most_left[dsu.merge(p-1, p)] = nx; p = nx; ans--; } }; for(int i=1; i> t; if(t == 1){ int v; cin >> v; v--; i64 x; cin >> x; for(auto path : hld.path(0, v)){ add_diff(path.first, -x); add_diff(path.second, x); } gapsum[v] += x; int cut_pos = segtree.min_left(N+1, [](SegtreeNode x){ return 0 < x.mingap; }) - 1; if(cut_pos >= 1){ int cut_v = hld.toVtx(cut_pos); clear_range(hld.subtree(cut_v).first, hld.subtree(cut_v).second); } } if(t == 2){ cout << ans << '\n'; } } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;