#include using namespace std; using ll = long long; template class Tree { public: int nodeNum; int isWeighted; int maxBit; int idx; vector> edge; vector> weight; vector depth; vector order; vector dist; vector parent; vector parentDist; vector> child; vector> childDist; vector> ancestor; vector> descendant; vector eulerTour; vector eulerTourDist; vector idxL; vector idxR; vector eulerTourDive,eulerTourFloat; vector eulerTourDiveDist,eulerTourFloatDist; vector idxLDive,idxLFloat; vector idxRDive,idxRFloat; Tree(const int nodeNum, const int isWeighted = 0, const int maxBit = 20) : nodeNum(nodeNum), isWeighted(isWeighted), maxBit(maxBit), edge(nodeNum), depth(nodeNum), order(nodeNum) { if(isWeighted) weight.resize(nodeNum); if(isWeighted) dist.resize(nodeNum); } //O(1) anytime void makeEdge(const int& from, const int& to, const T& w = 0) { edge[from].push_back(to); if(isWeighted) weight[from].push_back(w); } //O(N) anytime void makeDepth(const int root) { depth[root] = 0; if(isWeighted) dist[root] = 0; idx = 0; dfs1(root); order[idx++] = root; } //for makeDepth void dfs1(int from, int prev = -1){ for(int i = 0; i < edge[from].size(); ++i){ int to = edge[from][i]; if(to==prev) continue; depth[to] = depth[from] + 1; if(isWeighted) dist[to] = dist[from] + weight[from][i]; dfs1(to,from); order[idx++] = to; } } //O(N) anytime int diameter(void){ makeDepth(0); int tmp = max_element(depth.begin(), depth.end()) - depth.begin(); makeDepth(tmp); return *max_element(depth.begin(), depth.end()); } //O(N) after makeDepth void makeParent(void) { parent.resize(nodeNum); iota(parent.begin(),parent.end(),0); for (int i = 0; i < nodeNum; ++i) for (auto j : edge[i]) if (depth[i] > depth[j]) parent[i] = j; if(isWeighted) { parentDist.resize(nodeNum); for (int i = 0; i < nodeNum; ++i) for (int j = 0; j < edge[i].size(); ++j) if (depth[i] > depth[edge[i][j]]) parentDist[i] = weight[i][j]; } } //O(N) after makeDepth void makeChild(void) { child.resize(nodeNum); for (int i = 0; i < nodeNum; ++i) for (auto j : edge[i]) if (depth[i] < depth[j]) child[i].push_back(j); if(isWeighted) { childDist.resize(nodeNum); for (int i = 0; i < nodeNum; ++i) for (int j = 0; j < edge[i].size(); ++j) if (depth[i] < depth[edge[i][j]]) childDist[i].push_back(weight[i][j]); } } //O(NlogN) after makeDepth void makeAncestor(void) { ancestor.resize(nodeNum,vector(maxBit)); for (int i = 0; i < nodeNum; ++i) ancestor[i][0] = i; for (int i = 0; i < nodeNum; ++i) for (auto j : edge[i]) if (depth[i] > depth[j]) ancestor[i][0] = j; for (int bit = 1; bit < maxBit; ++bit) for (int i = 0; i < nodeNum; ++i) ancestor[i][bit] = ancestor[ancestor[i][bit - 1]][bit - 1]; } //O(N^2) after makeDepth void makeDescendant(void) { descendant.resize(nodeNum); for (int i = 0; i < nodeNum; ++i) descendant[i].push_back(i); for (int i = 0; i < nodeNum; ++i) for (auto j : edge[order[i]]) if (depth[order[i]] < depth[j]) for(auto k: descendant[j]) descendant[order[i]].push_back(k); } //O(logN) after makeAncestor int lca(int l, int r) { if (depth[l] < depth[r]) swap(l, r); int diff = depth[l] - depth[r]; for (int bit = 0; bit < maxBit; ++bit) if (diff & (1 << bit)) l = ancestor[l][bit]; if(l==r) return l; for (int bit = maxBit - 1; 0 <= bit; --bit) if(ancestor[l][bit]!=ancestor[r][bit]) l = ancestor[l][bit], r = ancestor[r][bit]; return ancestor[l][0]; } //O(N) after makeChild and makeParent void makeEulerTour(void){ dfs2(order[nodeNum-1]); idxL.resize(nodeNum); idxR.resize(nodeNum); for(int i = 0; i < eulerTour.size(); ++i) idxR[eulerTour[i]] = i; for(int i = eulerTour.size()-1; 0 <= i; --i) idxL[eulerTour[i]] = i; return; } //for makeEulerTour void dfs2(int from, int prev = -1){ eulerTour.push_back(from); if(isWeighted) eulerTourDist.push_back(parentDist[from]); for(int i = 0; i < child[from].size(); ++i){ int to = child[from][i]; dfs2(to,from); eulerTour.push_back(from); if(isWeighted) eulerTourDist.push_back(-childDist[from][i]); } } //O(NlogN) after makeEulerTour void makeEulerTourEdge(void) { eulerTourDive.push_back(order[nodeNum-1]); if(isWeighted) eulerTourDiveDist.push_back(0); for(int i = 1; i < eulerTour.size(); ++i) { int l = eulerTour[i-1]; int r = eulerTour[i]; if(depth[l] < depth[r]) { eulerTourDive.push_back(i); if(isWeighted) eulerTourDiveDist.push_back(eulerTourDist[i]); } else { eulerTourFloat.push_back(i); if(isWeighted) eulerTourFloatDist.push_back(eulerTourDist[i]); } } idxLDive.resize(nodeNum); idxRDive.resize(nodeNum); idxLFloat.resize(nodeNum); idxRFloat.resize(nodeNum); for(int i = 0; i < nodeNum; ++i) { int l = idxL[i]; int r = idxR[i]; idxLDive[i] = upper_bound(eulerTourDive.begin() ,eulerTourDive.end() ,l) - eulerTourDive.begin() ; idxRDive[i] = (upper_bound(eulerTourDive.begin() ,eulerTourDive.end() ,r) - eulerTourDive.begin()) -1; idxLFloat[i] = upper_bound(eulerTourFloat.begin(),eulerTourFloat.end(),l) - eulerTourFloat.begin() ; idxRFloat[i] = (upper_bound(eulerTourFloat.begin(),eulerTourFloat.end(),r) - eulerTourFloat.begin()) -1; idxRDive[i] = max(idxLDive[i]-1 ,idxRDive[i]); idxRFloat[i] = max(idxLFloat[i]-1,idxRFloat[i]); } } // iの部分木の頂点に加算するとき // [ idxL[i] ,idxR[i] ]に +val // [i]の頂点クエリ // [idxL[i],idxL[i]] // iの部分木の辺に加算するとき // [ idxLDive[i] ,idxRDive[i] ]に +val // [ idxLFloat[i] ,idxRFloat[i] ]に -val // [0,i]のパスクエリ // [ 0, idxLDive[i] ) + [0, idxLFloat[i]) }; //depth,dist //https://atcoder.jp/contests/abc126/tasks/abc126_d //lca //https://atcoder.jp/contests/abc014/tasks/abc014_4 //child //https://atcoder.jp/contests/abc133/tasks/abc133_e //eulerTour //https://yukicoder.me/problems/no/900 template class LazySegmentTree { size_t length; //セグメント木の最下段の要素の数(vectorの要素の数を超える2べきの数) size_t height; //セグメント木の高さ T unitNode; //nodeの単位元 T unitLazy; //lazyの単位元 vector node; //node vector lazy; //lazy vector width; //width function funcNode; //node同士の演算 function funcLazy; //lazy同士の演算 function funcMerge; //nodeとlazyの演算 public: //vectorで初期化 LazySegmentTree(const vector & vec, const T unitNode, const T unitLazy, function funcNode, function funcLazy,function funcMerge) : unitNode(unitNode), unitLazy(unitLazy), funcNode(funcNode),funcLazy(funcLazy),funcMerge(funcMerge) { for (length = 1,height = 0; length < vec.size(); length *= 2, height++); node.resize(2 * length, unitNode); lazy.resize(2 * length, unitLazy); for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i]; for (int i = length - 1; i >= 0; --i) node[i] = funcNode(node[(i<<1)+0],node[(i<<1)+1]); width.resize(2 * length, 0); for(int i = length; i < 2*length; ++i) for(int j = i, k = 1; j && !width[j] ; j >>= 1,k <<= 1) width[j] = k; } //同じinitで初期化 LazySegmentTree(const size_t num, const T unitNode, const T unitLazy, const T init, function funcNode, function funcLazy,function funcMerge) : unitNode(unitNode), unitLazy(unitLazy), funcNode(funcNode),funcLazy(funcLazy),funcMerge(funcMerge) { for (length = 1,height = 0; length < num; length *= 2, height++); node.resize(2 * length, unitNode); lazy.resize(2 * length, unitLazy); for (int i = 0; i < num; ++i) node[i + length] = init; for (int i = length - 1; i >= 0; --i) node[i] = funcNode(node[(i<<1)+0],node[(i<<1)+1]); width.resize(2 * length, 0); for(int i = length; i < 2*length; ++i) for(int j = i, k = 1; j && !width[j] ; j >>= 1,k <<= 1) width[j] = k; } //unitだけで初期化 LazySegmentTree(const size_t num, const T unitNode, const T unitLazy, function funcNode, function funcLazy,function funcMerge) : unitNode(unitNode), unitLazy(unitLazy), funcNode(funcNode),funcLazy(funcLazy),funcMerge(funcMerge) { for (length = 1,height = 0; length < num; length *= 2, height++); node.resize(2 * length, unitNode); lazy.resize(2 * length, unitLazy); width.resize(2 * length, 0); for(int i = length; i < 2*length; ++i) for(int j = i, k = 1; j && !width[j] ; j >>= 1,k <<= 1) width[j] = k; } void propagate(int k) { if(lazy[k] == unitLazy) return; node[k] = funcMerge(node[k],lazy[k],width[k]); if(k < length) lazy[2*k+0] = funcLazy(lazy[2*k+0],lazy[k]); if(k < length) lazy[2*k+1] = funcLazy(lazy[2*k+1],lazy[k]); lazy[k] = unitLazy; } //idx : 0-indexed void update(int a, int b, T x) { int l = a + length, r = b + length - 1; for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i); for(r++; l < r; l >>=1, r >>=1) { if(l&1) lazy[l] = funcLazy(lazy[l],x), propagate(l),l++; if(r&1) --r,lazy[r] = funcLazy(lazy[r],x), propagate(r); } l = a + length, r = b + length - 1; while ((l>>=1),(r>>=1),l) { if(lazy[l] == unitLazy) node[l] = funcNode(funcMerge(node[(l<<1)+0],lazy[(l<<1)+0],width[(l<<1)+0]),funcMerge(node[(l<<1)+1],lazy[(l<<1)+1],width[(l<<1)+1])); if(lazy[r] == unitLazy) node[r] = funcNode(funcMerge(node[(r<<1)+0],lazy[(r<<1)+0],width[(r<<1)+0]),funcMerge(node[(r<<1)+1],lazy[(r<<1)+1],width[(r<<1)+1])); } } //[l,r) T get(int a, int b) { int l = a + length, r = b + length - 1; for (int i = height; 0 < i; --i) propagate(l >> i), propagate(r >> i); T vl = unitNode, vr = unitNode; for(r++; l < r; l >>=1, r >>=1) { if(l&1) vl = funcNode(vl,funcMerge(node[l],lazy[l],width[l])),l++; if(r&1) r--,vr = funcNode(vr,funcMerge(node[r],lazy[r],width[r])); } return funcNode(vl,vr); } void print(){ // cout << "height" << " " << height << endl; // cout << "node" << endl; // for(int i = 1,j = 1; i < 2*length; ++i) { // cout << node[i] << " "; // if(i==((1<> N; Tree tree(N,1); for(int i = 0; i < N-1; ++i) { int u,v,w; cin >> u >> v >> w; tree.makeEdge(u,v,w); tree.makeEdge(v,u,w); } tree.makeDepth(0); tree.makeChild(); tree.makeParent(); tree.makeEulerTour(); tree.makeEulerTourEdge(); //区間加算 + 区間総和 function funcNode = [&](ll l,ll r){return l+r;}; function funcLazy = [&](ll l,ll r){return l+r;}; function funcMerge = [&](ll l,ll r,int c){return l+r*c;}; LazySegmentTree SegDive(tree.eulerTourDiveDist,0,0,funcNode,funcLazy,funcMerge),SegFloat(tree.eulerTourFloatDist,0,0,funcNode,funcLazy,funcMerge); int Q; cin >> Q; while(Q--) { int q; cin >> q; if(q==1) { int a,x; cin >> a >> x; SegDive.update(tree.idxLDive[a],tree.idxRDive[a]+1,x); SegFloat.update(tree.idxLFloat[a],tree.idxRFloat[a]+1,-x); } else { int b; cin >> b; cout << SegDive.get(0,tree.idxLDive[b])+SegFloat.get(0,tree.idxLFloat[b]) << endl; } } return 0; }