/* cd 9996-testcase g++ -std=gnu++17 -O2 -o val_potato p_val_potato.cpp for i in test_in/*; do echo "processing $i ..." #sed -e 's/\r$//g' $i | ./val_potato > ans.txt ./val_potato < $i > ans.txt diff ans.txt test_out/${i:8} done rm ans.txt rm val_potato cd ../ */ #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include #include "testlib.h" using namespace std; using ll = long long; #define all(p) p.begin(),p.end() #define rep(i,a,b) for(int i=(int)a;i<(int)b;i++) const int mod=998244353; const int MIN_N=2,MAX_N=3e5; const int MIN_Q=1,MAX_Q=3e5; const ll MIN_C=1,MAX_C=1e15; const int MIN_V=2; const ll MIN_X=1,MAX_X=1e9; int main(){ registerValidation(); const int N=inf.readInt(MIN_N,MAX_N); inf.readSpace(); const int Q=inf.readInt(MIN_Q,MAX_Q); inf.readEoln(); vector A(N-1),B(N-1); vector C(N-1); vector> G(N); rep(i,0,N-1){ A[i]=inf.readInt(1,N); inf.readSpace(); B[i]=inf.readInt(1,N); inf.readSpace(); C[i]=inf.readLong(MIN_C,MAX_C); inf.readEoln(); A[i]--,B[i]--; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } vector order={0},depth(N),wei(N),pare(N,-1); pare[0]=-2; rep(i,0,N){ //check connect ensure((int)order.size()>i); int a=order[i]; for(auto b:G[a]){ if(pare[b]==-1){ pare[b]=a; order.push_back(b); depth[b]=depth[a]+1; } } } rep(i,0,N){ int a=order[N-i-1]; for(auto b:G[a]){ if(pare[b]==a) wei[a]+=wei[b]; } wei[a]++; } vector n_C(N),V(N); rep(i,0,N-1){ if(depth[A[i]]>depth[B[i]]) swap(A[i],B[i]); n_C[B[i]]=C[i]; } swap(n_C,C); bool q2=0; vector remain(N,1); rep(rp,0,Q){ int t=inf.readInt(1,2); if(t==1){ inf.readSpace(); int u=inf.readInt(MIN_V,N); inf.readSpace(); ll x=inf.readLong(MIN_X,MAX_X); u--; ensure(remain[u]); while(u){ V[u]+=x; if(C[u]<=V[u]){ int tmp=u; order={u}; rep(i,0,(int)order.size()){ int a=order[i]; remain[a]=0; for(auto x:G[a]){ if(remain[x]&&pare[x]==a) order.push_back(x); } } while(u){ u=pare[u]; V[u]+=x; V[u]-=V[tmp]; wei[u]-=wei[tmp]; } break; } u=pare[u]; } } if(t==2){ q2=1; cout<