#include #include #include #include #include #include #include using namespace std; class HLD{ private: void dfs_sz(int v) { auto &es=G[v]; if(~par[v]) es.erase(find(es.begin(),es.end(),par[v])); for(int &u:es){ par[u]=v; dfs_sz(u); sub[v]+=sub[u]; if(sub[u]>sub[es[0]]) swap(u,es[0]); } } void dfs_hld(int v,int &pos) { vid[v]=pos++; inv[vid[v]]=v; for(int u:G[v]){ assert(u!=par[v]); nxt[u]=(u==G[v][0]?nxt[v]:u); dfs_hld(u,pos); } } public: vector< vector > G; // vid: vertex -> idx // inv: idx -> vertex vector vid,nxt,sub,par,inv; HLD(int n):G(n),vid(n,-1),nxt(n),sub(n,1),par(n,-1),inv(n){} void add_edge(int u,int v) { G[u].emplace_back(v); G[v].emplace_back(u); } void build(int r=0) { int pos=0; dfs_sz(r); nxt[r]=r; dfs_hld(r,pos); } int lca(int u,int v){ while(1){ if(vid[u]>vid[v]) swap(u,v); if(nxt[u]==nxt[v]) return u; v=par[nxt[v]]; } } template void for_each(int u,int v,const F& f) { while(1){ if(vid[u]>vid[v]) swap(u,v); f(max(vid[nxt[v]],vid[u]),vid[v]+1); if(nxt[u]!=nxt[v]) v=par[nxt[v]]; else break; } } template void for_each_edge(int u,int v,const F& f) { while(1){ if(vid[u]>vid[v]) swap(u,v); if(nxt[u]!=nxt[v]){ f(vid[nxt[v]],vid[v]+1); v=par[nxt[v]]; }else{ if(u!=v) f(vid[u]+1,vid[v]+1); break; } } } }; long op(long a,long b){return min(a,b);} long e(){return 1L;} long mp(long f,long x){return x+f;} long cmp(long f,long g){return f+g;} long id(){return 0L;} int N,Q; int U[3<<17],V[3<<17]; long C[3<<17]; bool deled[3<<17]; int cnt; void del(int u,const HLD&hld) { if(deled[u])return; deled[u]=true; cnt++; for(int v:hld.G[u])del(v,hld); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>Q; HLD hld(N); for(int i=0;i+1>U[i]>>V[i]>>C[i]; U[i]--,V[i]--; hld.add_edge(U[i],V[i]); } hld.build(); vectorinit(N); for(int i=0;i+1seg(init); vector >Rs; for(;Q--;) { int o;cin>>o; if(o==1) { int v,x; cin>>v>>x; v--; Rs.clear(); hld.for_each_edge(0,v,[&Rs](int l,int r){Rs.push_back(make_pair(l,r));}); for(pairp:Rs) { seg.apply(p.first,p.second,-x); //cout<<"["<p:Rs) { if(seg.prod(p.first,p.second)<=0) { int idx=seg.min_left(p.second,[](long val){return val>=1;}); assert(p.firstidx del(d,hld); long up=init[idx]-seg.get(idx); //cout<<"rec "<