#include using namespace std; typedef long long ll; typedef pair l_l; typedef pair i_i; template inline bool chmax(T &a, T b) { if(a < b) { a = b; return true; } return false; } template inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } #define EPS (1e-7) #define INF (1e9) #define PI (acos(-1)) //const ll mod = 1000000007; typedef vector> Graph; template class MinOp{ public: T operator () ( T a , T b ){ return min( a , b ); } }; // sparse table // static range semigroup query // time complexity: // OpFunc is binary operator: T x T -> T template struct SparseTable{ OpFunc op; int size; vector lg; vector > table; void init( const vector &array, OpFunc opfunc ){ int n = array.size(); op = opfunc; lg.assign( n + 1 , 0 ); for( int i = 1; i <= n; i++ ){ lg[i] = 31 - __builtin_clz( i ); } table.assign( lg[n] + 1, array ); for( int i = 1; i <= lg[n]; i++ ){ for( int j = 0; j < n; j++ ){ if( j + (1<<(i-1)) < n ){ table[i][j] = op( table[i-1][j] , table[i-1][j+(1<<(i-1))] ); } else { table[i][j] = table[i-1][j]; } } } } T query( int l , int r ){ assert( l < r ); return op( table[ lg[r-l] ][l], table[ lg[r-l] ][r-(1< struct PMORMQ{ vector a; SparseTable,MinOp > > sparse_table; vector > > lookup_table; vector block_type; int block_size, n_block; void init( const vector &array ){ a = array; int n = a.size(); block_size = max( 1, ( 31 - __builtin_clz( n ) ) / 2 ); while( n % block_size != 0 ){ a.push_back( a.back() + 1 ); n++; } n_block = n / block_size; vector > b( n_block, make_pair( INT_MAX, INT_MAX ) ); for( int i = 0; i < n; i++ ){ b[i/block_size] = min( b[i/block_size], make_pair( a[i], i ) ); } sparse_table.init( b, MinOp >() ); block_type.assign( n_block, 0 ); for( int i = 0; i < n_block; i++ ){ int cur = 0; for( int j = 0; j < block_size-1; j++ ){ int ind = i * block_size + j; if( a[ind] < a[ind+1] ){ cur |= 1 << j; } } block_type[i] = cur; } lookup_table.assign( 1 << (block_size-1), vector >( block_size, vector( block_size+1 ) ) ); for( int i = 0; i < (1<<(block_size-1)); i++ ){ for( int j = 0; j < block_size; j++ ){ int res = 0; int cur = 0; int pos = j; for( int k = j+1; k <= block_size; k++ ){ lookup_table[i][j][k] = pos; if( i & ( 1 << (k-1) ) ){ cur++; } else { cur--; } if( res > cur ){ pos = k; res = cur; } } } } } int query( int l, int r ){ // return position assert( l < r ); int lb = l / block_size; int rb = r / block_size; if( lb == rb ){ return lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ r % block_size ]; } int pl = lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ block_size ]; int pr = rb * block_size + lookup_table[ block_type[rb] ][0][ r % block_size ]; int pos = pl; if( r % block_size > 0 && a[pl] > a[pr] ){ pos = pr; } if( lb + 1 == rb ){ return pos; } int sp = sparse_table.query( lb+1, rb ).second; if( a[pos] > a[sp] ){ return sp; } return pos; } }; // LCA // time complexity: struct LCA{ int n; vector > G; PMORMQ rmq; int cnt; vector depth, id, in; void init( int size ){ n = size; G.assign( n, vector( 0 ) ); } void add_edge( int a , int b ){ G[a].push_back( b ); G[b].push_back( a ); } void dfs( int x , int p , int d ){ id[cnt] = x; depth.push_back( d ); in[x] = cnt++; for( int v : G[x] ){ if( v == p ){ continue; } dfs( v , x , d+1 ); id[cnt] = x; depth.push_back( d ); cnt++; } } void precalc( int root ){ cnt = 0; depth.clear(); in.assign( n, -1 ); id.assign( 2*n-1, -1 ); dfs( root, -1, 0 ); rmq.init( depth ); } int lca( int a , int b ){ int x = in[a]; int y = in[b]; if( x > y ){ swap( x , y ); } int pos = rmq.query( x, y + 1 ); return id[pos]; } }; vector pathes[100500]; vector children[100500]; ll cost[100500], nowcost[100500]; void DFS(int now, ll nowval) { nowval += nowcost[now]; cost[now] += nowval; nowcost[now] = 0; for(int &to : children[now]) DFS(to, nowval); } void DFS2(int now, ll nowval, ll nowsum) { cost[now] += nowsum; //cerr << "DFS" << now << " " << nowcost[now] << " " << cost[now] << endl; nowval += nowcost[now]; nowsum += nowval; nowcost[now] = 0; for(int &to : children[now]) { DFS2(to, nowval, nowsum); } } ll parent[100050]; ll dep[100050]; void initialize(int now, int from) { for(auto to : pathes[now]) { if(to == from) continue; children[now].push_back(to); parent[to] = now; dep[to] = dep[now] + 1; initialize(to, now); } } int ope, a, b; ll x; vector query; const int B = 500; ll u[100050], v[100050], w[100050]; LCA lca; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; lca.init(N); parent[0] = -1; Graph G(N); for(int i = 0; i <= N - 2; i++) { cin >> u[i] >> v[i] >> w[i]; G[u[i]].push_back(v[i]); G[v[i]].push_back(u[i]); pathes[u[i]].push_back(v[i]); pathes[v[i]].push_back(u[i]); } initialize(0, -1); for(int i = 0; i < N; i++) { for(auto to : children[i]) lca.add_edge(i, to); } lca.precalc(0); /* for(int i = 0; i < N; i++) { cerr << "---" << i << "---" << endl; for(auto v : children[i]) cerr << v << " "; cerr << endl; } */ for(int i = 0; i <= N - 2; i++) { if(parent[u[i]] == v[i]) swap(u[i], v[i]); nowcost[v[i]] += w[i]; } DFS(0, 0); //LCA.build(); ll Q; cin >> Q; int timer = 0; while(Q--) { //timer++; //if(timer >= 8e4) break; cin >> ope; if(ope == 1) { cin >> a >> x; query.emplace_back(a, x); nowcost[a] += x; } else { cin >> b; ll ans = cost[b]; for(l_l now : query) { if(lca.lca(now.first, b) == now.first) { ans += now.second * (dep[b] - dep[now.first]); } } cout << ans << "\n"; } if((int)query.size() == B) { query.clear(); DFS2(0, 0, 0); } } return 0; }