#include using namespace std; #define endl '\n' #define ALL(a) (a).begin(),(a).end() #define ALLR(a) (a).rbegin(),(a).rend() #define spa << " " << #define lfs <= (ll)(m); i--) using ll = long long; using ld = long double; const ll MOD = 1e9+7; //const ll MOD = 998244353; const ll INF = 1e18; using P = pair; template void chmin(T &a,T b){if(a>b)a=b;} template void chmax(T &a,T b){if(a void ans(bool x,T1 y,T2 z){if(x)cout< void debug(vector>v,ll h,ll w){for(ll i=0;iv,ll h,ll w){for(ll i=0;i void debug(vectorv,ll n){if(n!=0)cout< vector>vec(ll x, ll y, T w){ vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} template vectordx={1,0,-1,0,1,1,-1,-1}; vectordy={0,1,0,-1,1,-1,1,-1}; template vector make_v(size_t a,T b){return vector(a,b);} template auto make_v(size_t a,Ts... ts){ return vector(a,make_v(ts...)); } struct edge{ ll to,cost; edge(ll t,ll c):to(t),cost(c){}; }; struct HLD{ ll n, root; vectorsz;//部分木サイズ vectordepth,par,hv_chi; vectorhead; vector>g;//隣接リスト vectoredges;//データ構造に乗せるedge列 vectoridx;//edge列のindexを下側の頂点から求めるor頂点列のindex vectorsubidx;//部分木に含まれる最後の頂点+1 HLD(vector>G,ll r) :g(G),n(G.size()),root(r){ depth.assign(n,-1),par.assign(n,-1),hv_chi.assign(n,-1); sz.assign(n,-1),head.assign(n,-1),idx.assign(n,-1); subidx.assign(n,-1); edges.emplace_back(0,0); idx[root] = 0; dfs_sz(root,0); dfs_hl(root); subidx[root]=edges.size(); } ll dfs_sz(ll k, ll d){ depth[k] = d; ll sum_sz = 0; ll max_sz = 0,idx = -1; for(ll i=0;i depth[head[q]])swap(p,q); if(head[p] == head[q])break; q = par[head[q]]; } if(depth[p] > depth[q])swap(p,q); return p; } vector>query_path(ll p,ll q,bool isEdge){ vectorv = {p,q}; ll r=lca(p,q); vector>ret; for(ll i=0;i<2;i++){ while(1){ if(isEdge&&v[i]==r)break; if(head[v[i]]==head[r]){ ret.emplace_back(idx[r]+(isEdge?1:i),idx[v[i]]+1); break; } ret.emplace_back(idx[head[v[i]]],idx[v[i]]+1); v[i] = par[head[v[i]]]; } } return ret; } pairquery_subtree(ll p,bool isEdge){ return MP(idx[p]+1,subidx[p]); } }; template struct LazySegmentTree{ using F = function; vector data, lazy; ll n,lastlen = 1; F func = [](T a, T b){return a+b;}; T iden = 0; //identity element F f_lazy = [](T a, T b){return a+b;}; T iden_l = 0; F f_trans = [](T a, ll range){return a*(ll)range;}; LazySegmentTree(vector v){ n = (ll)v.size(); while(lastlen < n)lastlen *= 2; data.assign(lastlen*2-1,iden); lazy.assign(lastlen*2-1,iden_l); for(ll i=0;i=0;i--){ data[i] = func(data[2*i+1], data[2*i+2]); } } void eval(ll k, ll left, ll right){ if(lazy[k] != iden_l){ data[k] = f_lazy(data[k], f_trans(lazy[k],right-left)); if(k <= lastlen - 2){ lazy[2*k+1] = f_lazy(lazy[2*k+1],lazy[k]); lazy[2*k+2] = f_lazy(lazy[2*k+2],lazy[k]); } lazy[k] = iden_l; } } void update(ll a,ll b,T x,ll point=0LL, ll left=0LL,ll right=-1LL){ if(right<0)right=lastlen; eval(point,left,right); if(b <= left || right <= a); else if(a <= left && right <= b ){ lazy[point] = x; eval(point,left,right); } else{ update(a,b,x,point*2+1, left, (left+right)/2); update(a,b,x,point*2+2, (left+right)/2, right); data[point] = func(data[2*point+1], data[2*point+2]); } } T query(ll a,ll b,ll point=0LL,ll left=0LL,ll right=-1LL){ if(right<0)right=lastlen; T ret = iden; eval(point,left,right); if(b <= left || right <= a); else if(a <= left && right <= b ){ ret = func(ret,data[point]); } else{ T p=query(a,b,point*2+1, left, (left+right)/2); T q=query(a,b,point*2+2, (left+right)/2, right); data[point] = func(data[2*point+1], data[2*point+2]); ret = func(ret,p); ret = func(ret,q); } return ret; } void print(){ ll num=0; for(ll i=lastlen;i>0;i/=2)num++; ll tmp=1; for(ll i=0;i>n; vector>g(n); for(ll i=0;i>u>>v>>c; g[u].emplace_back(v,c); g[v].emplace_back(u,c); } HLD hld(g,0); vectores; rep(i,0,hld.edges.size())es.PB(hld.edges[i].cost); LazySegmentTreesegtree(es); ll q;cin>>q; while(q--){ ll sw;cin>>sw; if(sw==1){ ll a,x;cin>>a>>x; auto p=hld.query_subtree(a,true); segtree.update(p.fi,p.se,x); } else { ll a;cin>>a; auto v=hld.query_path(0,a,true); ll ret=0; rep(i,0,v.size())ret+=segtree.query(v[i].fi,v[i].se); cout<