#include #include using namespace std; using namespace atcoder; struct hldTree { hldTree (int _n = 0, int _root = 0) : n(_n), root(_root) { init();} void add_edge(int u, int v, int id){ // id must be 0 <= id < n es[u].emplace_back(v,id); es[v].emplace_back(u,id); } void remake(int new_n, int new_root = 0){ es.clear(); size.clear(); par.clear(); dep.clear(); up.clear(); down.clear(); nxt.clear(); order.clear(); edges.clear(); whose.clear(); n = new_n, root = new_root; init(); } void build(){ dfs_init(root); int t = 0; dfs_hld(root,t); } int lca(int u, int v){ while (nxt[u] != nxt[v]){ if (down[u] < down[v]) swap(u,v); u = par[nxt[u]]; } return dep[u] < dep[v] ? u : v; } int dist(int u, int v){ return dep[u] + dep[v] - 2 * dep[lca(u,v)]; } int parent(int v){ return par[v];} int depth(int v){ return dep[v];} int subtree_size(int v){ return size[v];} int pre(int v){ return down[v];} int post(int v){ return up[v];} int ord(int i){ return order[i];} int who(int i){ return whose[i];} int edge(int v){ return edges[v];} template void path_query(int u, int v, bool vertex, const F &f){ // f is function takes (left, right) as argument, range = [left,right). int l = lca(u,v); for (auto &p : ascend(u,l)){ int s = p.first + 1, t = p.second; // p.first + 1 : depth(p.first) > depth(p.second), so [p.second,p.first] = [p.second,p.first+1) s > t ? f(t,s) : f(s,t); } if (vertex) f(down[l],down[l]+1); // vertex is true : query is for point for (auto &p : descend(l,v)){ int s = p.first, t = p.second + 1; // p.second +1 : depth(p.first) < depth(p.second), so [p.first,p.second] = [p.first,p.second+1) s > t ? f(t,s) : f(s,t); } } template void path_noncommutative_query(int u, int v, bool vertex, const F &f){ // op(l,r) != op(r,l), so prod[u->...->v] != prod[v->...->u] int l = lca(u,v); for (auto &p : ascend(u,l)){ int s = p.first + 1, t = p.second; // p.first + 1 : depth(p.first) > depth(p.second), so [p.second,p.first] = [p.second,p.first+1) f(s,t); // le > ri ok } if (vertex) f(down[l],down[l]+1); // vertex is true : query is for point for (auto &p : descend(l,v)){ int s = p.first, t = p.second + 1; // p.second +1 : depth(p.first) < depth(p.second), so [p.first,p.second] = [p.first,p.second+1) f(s,t); // le > ri ok } } template void subtree_query(int v, bool vertex, const F &f){ f(down[v] + (vertex ? 0 : 1), up[v]); } const vector>& operator()(int idx) const { return es[idx];} private: int n, root; vector>> es; vector size, par, dep, up, down, nxt; // nxt[i] : most shallow vertex in connected component of vertex i vector order, edges, whose; // order[i] is ith vertex visited on Euler tour, vertex v has edges[v] (root has no edge), edges^-1 = whose void init(){ es.resize(n); size.resize(n,0); par.resize(n,root); dep.resize(n,0); up.resize(n,-1); down.resize(n,-1); nxt.resize(n,root); order.resize(n,-1); edges.resize(n,-1); whose.resize(n,-1); } void dfs_init(int cur){ size[cur] = 1; for (auto &e : es[cur]){ if (e.first == par[cur]){ if (es[cur].size() >= 2 && e.first == es[cur][0].first){ swap(es[cur][0],es[cur][1]); // if cur is not leaf, vs[cur][0] is not cur's parent } else continue; } par[e.first] = cur; edges[e.first] = e.second; whose[e.second] = e.first; dep[e.first] = dep[cur] + 1; dfs_init(e.first); size[cur] += size[e.first]; if (size[e.first] > size[es[cur][0].first]){ swap(e,es[cur][0]); // to maximize vs[cur][0]'s subtree_size } } } void dfs_hld(int cur, int &tnow){ down[cur] = tnow++; // down[0,...,n-1] is permutation of 0,...,n-1 order[down[cur]] = cur; for (auto e : es[cur]){ if (e.first == par[cur]) continue; nxt[e.first] = (e.first == es[cur][0].first ? nxt[cur] : e.first); dfs_hld(e.first,tnow); } up[cur] = tnow; // up[0,...,n-1] is NOT permutation, up[*] <= n } vector> ascend(int u, int v) const { // [u,v), depth[u] > depth[v] vector> res; while (nxt[u] != nxt[v]){ res.emplace_back(down[u],down[nxt[u]]); // [s1,t1], [s2,t2], ... u = par[nxt[u]]; } if (u != v) res.emplace_back(down[u],down[v]+1); // [s,t). v is not in the range (down[] is ordered opposite direction of depth) return res; } vector> descend(int u, int v) const { // (u,v], depth[u] < depth[v] if (u == v) return {}; if (nxt[u] == nxt[v]){ return {pair(down[u]+1,down[v])}; // (s,t]. u is not in the range } vector> res = descend(u,par[nxt[v]]); res.emplace_back(down[nxt[v]],down[v]); // [s1,t1], [s2,t2], ... return res; } }; using ll = long long; using ar = array; const ll linf = 1e16; hldTree g; ar op1(ar a, ar b){ if (a[0] <= 0 && b[0] <= 0){ return (g.depth(a[1]) > g.depth(b[1]) ? a : b); } return (a[0] < b[0] ? a : b); } ar e1(){ return {linf,0}; } ar mapping1(ll f, ar x){ return {x[0]+f,x[1]}; } ll composition1(ll f, ll g){ return f + g; } ll ideal1(){ return 0; } ar op2(ar a, ar b){ return {a[0]+b[0],a[1]+b[1]}; } ar e2(){ return {0,0}; } ar mapping2(int f, ar x){ if (f == -1) return x; return {0,0}; } int composition2(int f, int g){ if (f == -1) return g; return f; } int ideal2(){ return -1; } int main(){ int n, q; cin >> n >> q; vector cs(n-1); g = hldTree(n); for (int i = 0; i < n-1; i++){ int u, v; cin >> u >> v >> cs[i]; u--, v--; g.add_edge(u,v,i); } g.build(); lazy_segtree seg1(n); lazy_segtree seg2(n); for (int v = 0; v < n; v++){ for (auto [u, id] : g(v)){ if (g.depth(v) > g.depth(u)) continue; seg1.set(g.pre(u),{cs[id],u}); } seg2.set(g.pre(v),{1,0}); } ll num = 0; auto add = [&](int l, int r){ if (l > r) swap(l,r); seg1.apply(l,r,num); }; ar dele = e1(); auto del_edge = [&](int l, int r){ if (l > r) swap(l,r); dele = op1(dele,seg1.prod(l,r)); }; ar sum = e2(); auto count = [&](int l, int r){ if (l > r) swap(l,r); sum = op2(sum,seg2.prod(l,r)); }; auto update = [&](int l, int r){ if (l > r) swap(l,r); seg2.apply(l,r,0); }; while (q--){ int t; cin >> t; if (t == 2){ cout << seg2.all_prod()[0] << endl; continue; } int v; cin >> v; v--; ll x; cin >> x; // add apple seg2.set(g.pre(v),{1,seg2.get(g.pre(v))[1]+x}); // decrease by x num = -x; g.path_query(0,v,false,add); // find deleted edge dele = e1(); g.path_query(0,v,false,del_edge); if (dele[0] > 0) continue; // delete the edge int f = dele[1]; sum = e2(); g.subtree_query(f,true,count); g.subtree_query(f,true,update); // increase by sum[1] : droped apples num = sum[1]; g.path_query(0,v,false,add); } }