#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 x,ll y):to(x),cost(y){}; edge():to(0LL),cost(0LL){}; }; //辺のオイラーツアー struct Eulertour{ ll n,m; ll root=0; vectorvertex;//頂点列 vector>data;//辺情報 vectordepth;//0から vector>G; vector>index;//<最左index,最右index> Eulertour(vector>g):G(g),n(g.size()){ depth.assign(n,-1); index.assign(n,make_pair(10*n,10*n)); dfs(root,0); m=vertex.size(); } void dfs(ll k,ll d){ depth[k]=d; for(ll i=0;ioutput(){//辺のコスト列を返す vectorret(m); for(ll i=0;ioutput2(){//辺のコスト列と正の辺の個数のペア vector

ret(m); for(ll i=0;i struct LazySegmentTree{ using F = function; vector data, lazy; ll n,lastlen = 1; F func = [](T a, T b){return MP(a.fi+b.fi,a.se+b.se);}; T iden = MP(0,0); //identity element function f_lazy = [](T a, T b,ll range){return MP(a.fi+b.fi*(2*a.se-range),a.se);}; T iden_l = MP(0,0); function f_trans = [](T a, ll range){return a;}; 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),right-left); if(k <= lastlen - 2){ lazy[2*k+1] = f_lazy(lazy[2*k+1],lazy[k],right-left); lazy[2*k+2] = f_lazy(lazy[2*k+2],lazy[k],right-left); } 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); } Eulertour et(g); auto v=et.output2(); LazySegmentTree

segtree(v); ll q;cin>>q; while(q--){ ll sw;cin>>sw; if(sw==1){ ll a,x;cin>>a>>x; ll l=et.index[a].fi,r=et.index[a].se; segtree.update(l,r,MP(x,0)); } else { ll a;cin>>a; ll l=et.index[0].fi; ll r=et.index[a].fi; cout<