結果

問題 No.900 aδδitivee
ユーザー kyort0nkyort0n
提出日時 2019-10-04 22:35:38
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
8,320 KB
testcase_01 AC 3 ms
8,320 KB
testcase_02 AC 3 ms
8,320 KB
testcase_03 AC 3 ms
8,448 KB
testcase_04 AC 5 ms
8,320 KB
testcase_05 AC 4 ms
8,320 KB
testcase_06 AC 3 ms
8,192 KB
testcase_07 AC 1,771 ms
36,068 KB
testcase_08 AC 1,751 ms
36,076 KB
testcase_09 AC 1,744 ms
36,196 KB
testcase_10 AC 1,804 ms
36,192 KB
testcase_11 AC 1,765 ms
35,928 KB
testcase_12 AC 1,801 ms
36,072 KB
testcase_13 AC 1,825 ms
36,068 KB
testcase_14 AC 1,776 ms
36,196 KB
testcase_15 AC 1,787 ms
36,064 KB
testcase_16 AC 1,788 ms
36,068 KB
testcase_17 AC 1,783 ms
36,204 KB
testcase_18 AC 1,742 ms
36,132 KB
testcase_19 AC 1,750 ms
36,068 KB
testcase_20 AC 1,748 ms
36,196 KB
testcase_21 AC 1,784 ms
36,068 KB
testcase_22 AC 745 ms
41,532 KB
testcase_23 AC 735 ms
41,404 KB
testcase_24 AC 733 ms
41,400 KB
testcase_25 AC 737 ms
41,428 KB
testcase_26 AC 725 ms
41,400 KB
testcase_27 AC 746 ms
41,304 KB
testcase_28 AC 747 ms
41,400 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 -> T
template<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 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: <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;
}
0