結果

問題 No.901 K-ary εxtrεεmε
コンテスト
ユーザー _____TAB_____
提出日時 2019-10-04 23:15:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,472 bytes
コンパイル時間 1,266 ms
コンパイル使用メモリ 93,596 KB
最終ジャッジ日時 2025-01-07 20:48:14
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <cstdio>
#include <set>
using namespace std;

void dfs(const vector<vector<pair<long long,int>>> &G, int v, int p, vector<int> &D){
  for(auto e : G[v]){
    long long w;
    int v_;
    tie(w,v_) = e;
    if(v_ == p) continue;
    D[v_] = D[v]+1;
    dfs(G,v_,v,D);
  }
}

int main(){
  int N;
  cin >> N;
  vector<vector<pair<long long,int>>> G(N);
  for(int i = 0; i < N-1; ++i){
    int u, v, w;
    cin >> u >> v >> w;
    G[u].emplace_back(w,v);
    G[v].emplace_back(w,u);
  }
  vector<int> D(N);
  dfs(G,0,-1,D);
  vector<vector<pair<long long,int>>> V(20,vector<pair<long long,int>>(N));
  for(int i = 0; i < N; ++i){
    for(auto e : G[i]){
      int v_ = e.second;
      if(D[i] == D[v_]+1){
        V[0][i] = e;
      }
    }
  }
  // cerr << "D : ";
  // for(auto d : D) cerr << d << " ";
  // cerr << endl;
  for(int i = 1; i < 20; ++i){
    for(int j = 0; j < N; ++j){
      auto s = V[i-1][j];
      auto t = V[i-1][s.second];
      V[i][j] = {s.first+t.first,t.second};
    }
  }
  auto solve = [&](vector<int> X){
                 long long ret = 0;
                 set<int> S;
                 for(auto x : X) S.insert(x);
                 while(true){
                   int max_d = 0, min_d = 100;
                   for(auto v : S){
                     max_d = max(max_d, D[v]);
                     min_d = min(min_d, D[v]);
                   }
                   if(max_d == min_d) break;
                   set<int> S_;
                   for(auto v : S){
                     if(D[v] < max_d){
                       S_.insert(v);
                       continue;
                     }
                     ret += V[0][v].first;
                     S_.insert(V[0][v].second);
                   }
                   S = S_;
                 }
                 while(S.size() > 1){
                   for(int k = 19; k >= 0; --k){
                     set<int> S_;
                     for(auto v : S){
                       S_.insert(V[k][v].second);
                     }
                     if(S_.size() == S.size()){
                       for(auto v : S){
                         ret += V[k][v].first;
                       }
                       swap(S,S_);
                     }
                     // if(V[k][u].second != V[k][v].second){
                     //   ret += V[k][u].first + V[k][v].first;
                     //   u = V[k][u].second;
                     //   v = V[k][v].second;
                     // }
                   }
                   set<int> S_;
                   for(auto v : S){
                     ret += V[0][v].first;
                     S_.insert(V[0][v].second);
                   }
                   swap(S,S_);
                 }
                 return ret;
               };
  int Q;
  cin >> Q;
  while(Q--){
    int k;
    cin >> k;
    vector<int> X(k);
    for(int i = 0; i < k; ++i) cin >> X[i];
    // auto p = solve(X[0],X[1]);
    // auto q = solve(X[1],X[2]);
    // auto r = solve(X[2],X[0]);
    // auto s = solve(q.second,X[0]);
    // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],X[1],p.first,p.second);
    // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],X[2],r.first,r.second);
    // fprintf(stderr,"solve(%d,%d) = (%lld,%d)\n",X[0],q.second,s.first,s.second);
    // long long ans = p.first + r.first - s.first;
    long long ans = solve(X);
    cout << ans << endl;
  }
}
0