#include #include #include #include using namespace std; typedef long long ll; typedef pair Pa; struct edge{ int to; ll w; }; template class LazySegmentTree{ private: using F = function; using G = function; using H = function; using P = function; int sz,height; vector data; vector lazy; F func; G op; H mergeOp; P multmergeOp; Monoid e; OpMonoid op_e; public: LazySegmentTree(){} LazySegmentTree(int n, const F f, const G g, const H h, const P p, const Monoid &e, const OpMonoid op_e) :func(f), op(g), mergeOp(h), multmergeOp(p), e(e), op_e(op_e){ sz = 1; while(sz0;k--){ data[k] = func(data[2*k],data[2*k+1]); } } //kの子に長さlenの遅延を伝搬 void propagate(int k, int len){ if(lazy[k]!=op_e){ if(k>1),update(a,b,x,2*k+1,(l+r)>>1,r)); } } Monoid update(int a, int b, const OpMonoid &x){ /* a += sz; b += sz-1; for(int i=height;i>0;i--) propagate(a>>i,1<<(height-i)),propagate(b>>i,1<<(height-i)); b++; Monoid res1 = e,res2 = e; while(a>= 1; b >>= 1; } return func(res1,res2);*/ return update(a,b,x,1,0,sz); } //クエリ回答 Monoid query(int a, int b, int k, int l, int r){ propagate(k,r-l); if(r<=a || b<=l){ return e; }else if(a<=l && r<=b){ return data[k]; }else{ return func(query(a,b,2*k,l,(l+r)>>1),query(a,b,2*k+1,(l+r)>>1,r)); } } Monoid query(int a, int b){ return query(a,b,1,0,sz); } Monoid operator[](const int &k){ return query(k,k+1); } }; const auto fm = [](Pa a, Pa b){ return Pa(a.first+b.first,a.second+b.second); }; const auto fa = [](Pa a, ll b){ return Pa(a.first + b*a.second,a.second); }; const auto fl = [](ll d, ll e){ return d+e; }; const auto mult = [](ll x,ll y){ return x; }; class EulerTour{ private: vector> v; vector> parent; vector depth; vector ds,us; LazySegmentTree seg; //uからvに降りるパスが、区間[ds[u]+1,ds[v]+1)に対応 void dfs(int n,int m,int d,int &id){ parent[0][n] = m; depth[n] = d; for(auto x:v[n]){ if(x.to!=m){ ds[x.to] = id++; seg.set(id-1,Pa(x.w,1)); dfs(x.to,n,d+1,id); us[x.to] = id++; seg.set(id-1,Pa(-x.w,-1)); } } } public: EulerTour(int N,int root,vector>& tree){ v = tree; parent = vector>(20,vector(N,0)); depth = ds = us = vector(N,0); seg.init(2*N+1,fm,fa,fl,mult,Pa(0,0),0); int id = 1; dfs(root,-1,0,id); us[root] = id; seg.build(); for(int j=0;j+1<20;j++){ for(int i=0;idepth[m]) swap(n,m); for(int j=0;j<20;j++){ if((depth[m]-depth[n]) >> j&1) m = parent[j][m]; } if(n==m) return n; for(int j=19;j>=0;j--){ if(parent[j][n]!=parent[j][m]){ n = parent[j][n]; m = parent[j][m]; } } return parent[0][n]; } void update(int node, ll x){ // cerr << node << " " << ds[node] << " " << us[node] << endl; seg.update(ds[node]+1,us[node],x); } long long query(int node){ // cerr << node << " " << us[node] << endl; return seg.query(0,us[node]).first; } int dep(int n){return depth[n];} int getds(int u){return ds[u];} int getus(int u){return us[u];} }; int main(){ int N; cin >> N; vector> v(N); for(int i=0;i> s >> t >> w; v[s].push_back({t,w}); v[t].push_back({s,w}); } EulerTour et(N,0,v); int Q; cin >> Q; for(int i=0;i> t; if(t==1){ int a; ll x; cin >> a >> x; et.update(a,x); }else{ int a; cin >> a; cout << et.query(a) << endl; } } }