結果
| 問題 | No.900 aδδitivee |
| ユーザー |
 kyort0n
|
| 提出日時 | 2019-10-04 22:35:38 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,825 ms / 2,000 ms |
| コード長 | 6,995 bytes |
| コンパイル時間 | 2,704 ms |
| コンパイル使用メモリ | 201,448 KB |
| 実行使用メモリ | 41,532 KB |
| 最終ジャッジ日時 | 2024-10-03 08:06:38 |
| 合計ジャッジ時間 | 36,484 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll, ll> l_l;typedef pair<int, int> i_i;template<class T>inline bool chmax(T &a, T b) {if(a < b) {a = b;return true;}return false;}template<class T>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<vector<ll>> Graph;template<class T>class MinOp{public:T operator () ( T a , T b ){ return min( a , b ); }};// sparse table// static range semigroup query// time complexity: <O(n log n), O(1)>// OpFunc is binary operator: T x T -> Ttemplate<typename T, typename OpFunc>struct SparseTable{OpFunc op;int size;vector<int> lg;vector<vector<T> > table;void init( const vector<T> &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<<lg[r-l])] );}};// plus minus one Range Minimum Query// time complexity: <O(n), O(1)>struct PMORMQ{vector<int> a;SparseTable<pair<int,int>,MinOp<pair<int,int> > > sparse_table;vector<vector<vector<int> > > lookup_table;vector<int> block_type;int block_size, n_block;void init( const vector<int> &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<pair<int,int> > 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<pair<int,int> >() );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<vector<int> >( block_size, vector<int>( 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 positionassert( 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: <O(n), O(1)>struct LCA{int n;vector<vector<int> > G;PMORMQ rmq;int cnt;vector<int> depth, id, in;void init( int size ){n = size;G.assign( n, vector<int>( 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<int> pathes[100500];vector<int> 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<l_l> query;const int B = 80;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++;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;}