#386948 (C++14) No.901 K-ary εxtrεεmε

• 問題: No.901 K-ary εxtrεεmε
• ユーザー: kyort0n
• 提出日時: 2019-10-04 23:50:58
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2,900 ms / 3,000 ms
• コード長: 7,715 bytes
• コンパイル時間: 2,757 ms
• コンパイル使用メモリ: 199,300 KB
• 実行使用メモリ: 41,392 KB
• 最終ジャッジ日時: 2024-10-03 09:54:15
• 合計ジャッジ時間: 23,151 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 1
other	AC * 29

ソースコード

#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 = 500;
ll u[100050], v[100050], w[100050];
ll num[100500];

void search(int now) {
  for(auto to : children[now]) {
    search(to);
    num[now] += num[to];
  }
}

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);
    for(int i = 0; i < N; i++) {
      //cerr << i << " " << cost[i] << endl;
    }
    //LCA.build();
    ll Q;
    cin >> Q;
    int timer = 0;
    while(Q--) {
      //timer++;
      //if(timer >= 8e4) break;
      ll n;
      cin >> n;
      if(n <= 50) {
        vector<int> v(n), u(n);
        for(int i = 0; i < n; i++) cin >> v[i];
        ll ans = 0;
        ll parent = v[0];
        for(int i = 0; i < n; i++) {
          parent = lca.lca(parent, v[i]);
        }
        for(int i = 0; i < n; i++) {
          int now = parent;
          for(int j = 0; j < i; j++) {
            u[j] = lca.lca(v[i], v[j]);
            if(lca.lca(now, u[j]) == now) now = u[j];
          }
          ans += cost[v[i]] - cost[now];
        }
        cout << ans << "\n";
      } else {
        for(int i = 0; i < N; i++) num[i] = 0;
        int K = n;
        while(n--) {
          ll v;
          cin >> v;
          num[v]++;
        }
        search(0);
        ll ans = 0;
        for(int i = 0; i < N - 1; i++) {
          int nownum = min(num[u[i]], num[v[i]]);
          if(0 < nownum && nownum < K) ans += w[i];
        }
        cout << ans << "\n";
      }
    }
    return 0;
}