結果

問題 No.898 tri-βutree
ユーザー goodbatongoodbaton
提出日時 2019-10-05 01:09:38
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 492 ms / 4,000 ms
コード長 4,045 bytes
コンパイル時間 1,610 ms
コンパイル使用メモリ 122,204 KB
実行使用メモリ 39,004 KB
最終ジャッジ日時 2024-11-08 22:39:44
合計ジャッジ時間 11,300 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 158 ms
39,004 KB
testcase_01 AC 6 ms
8,448 KB
testcase_02 AC 6 ms
8,448 KB
testcase_03 AC 6 ms
8,448 KB
testcase_04 AC 6 ms
8,448 KB
testcase_05 AC 6 ms
8,448 KB
testcase_06 AC 6 ms
8,576 KB
testcase_07 AC 468 ms
33,500 KB
testcase_08 AC 479 ms
33,632 KB
testcase_09 AC 492 ms
33,632 KB
testcase_10 AC 481 ms
33,632 KB
testcase_11 AC 481 ms
33,504 KB
testcase_12 AC 491 ms
33,504 KB
testcase_13 AC 471 ms
33,628 KB
testcase_14 AC 460 ms
33,504 KB
testcase_15 AC 463 ms
33,504 KB
testcase_16 AC 474 ms
33,500 KB
testcase_17 AC 484 ms
33,508 KB
testcase_18 AC 478 ms
33,632 KB
testcase_19 AC 483 ms
33,632 KB
testcase_20 AC 484 ms
33,500 KB
testcase_21 AC 453 ms
33,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/*Lowest Common Ancstor*/
struct LCA{
  int n;
  vector<vector<int>> tree, parent;
  vector<int> depth;
  int max_log;

  LCA(int n): n(n), tree(n), depth(n, -1) {
    max_log = 0;
    for(int i=1; i<=n*2; i*=2) max_log++;
    parent.assign(max_log, vector<int>(n, -1));
  }

  void add_edge(int u, int v) {
    tree[u].push_back(v);
    tree[v].push_back(u);
  }

  void dfs(int now, int p, int d){
    parent[0][now] = p;
    depth[now] = d;

    for(int to : tree[now])
      if(to != p)
        dfs(to, now, d+1);
  }

  void build(int root){
    dfs(root, -1, 0);

    for(int i=0; i<max_log-1; i++)
      for(int j=0; j<n; j++)
        parent[i+1][j] = parent[i][j] == -1 ? -1 : parent[i][parent[i][j]];
  }

  int query(int a, int b){
    if(depth[a] > depth[b]) swap(a, b);

    for(int i=0; i<max_log; i++)
      if((depth[b] - depth[a]) >> i & 1)
        b = parent[i][b];

    if(a == b) return a;

    for(int i=max_log-1; i>=0; i--){
      if(parent[i][a] != parent[i][b]){
        a = parent[i][a];
        b = parent[i][b];
      }
    }

    return parent[0][a];
  }
};


vector<pair<int,int>> G[SIZE];
ll dist[SIZE];
int parent[18][SIZE];
int eulerIn[SIZE], eulerOut[SIZE], counter = 0;

void dfs(int now, int back = -1, ll d = 0) {
  dist[now] = d;
  parent[0][now] = back;
  eulerIn[now] = counter++;

  for (auto p : G[now]) {
    int to = p.first;
    int cost = p.second;
    if (to == back) continue;

    dfs(to, now, d + cost);
  }

  eulerOut[now] = counter++;
}


int main(){
  int N, Q;

  scanf("%d", &N);

  LCA lca(N);

  for (int i=0; i<N-1; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[v].push_back({u, w});
    G[u].push_back({v, w});

    lca.add_edge(u, v);
  }

  lca.build(0);
  dfs(0);

  for (int i=0; i<18-1; i++) {
    for (int j=0; j<N; j++) {
      if (parent[i][j] == -1)
        parent[i+1][j] = -1;
      else
        parent[i+1][j] = parent[i][parent[i][j]];
    }
  }

  scanf("%d", &Q);

  for (int i=0; i<Q; i++) {
    int K;
    //scanf("%d", &K);
    K = 3;

    int g = -1;
    set<int> ss;
    priority_queue<pair<ll, int>> pq;

    for (int j=0; j<K; j++) {
      int x;
      scanf("%d", &x);
      if (j == 0) g = x;
      else g = lca.query(g, x);
      ss.insert(eulerIn[x]);
      pq.push({dist[x], x});
    }

    ss.insert(eulerIn[g]);

    ll ans = 0;

    while (ss.size() > 1) {
      auto p = pq.top();
      pq.pop();
      int x = p.second;
      int tmp = x;

      ss.erase(ss.find(eulerIn[x]));

      for (int j=17; j>=0; j--) {
        if (parent[j][tmp] == -1) continue;

        int q = parent[j][tmp];
        auto it = ss.lower_bound(eulerIn[q]);

        if (it == ss.end() || eulerOut[q] < *it)
          tmp = q;
      }

      auto it = ss.lower_bound(eulerIn[tmp]);
      if (it == ss.end() || eulerOut[tmp] < *it)
        tmp = parent[0][tmp];

      ans += dist[x] - dist[tmp];

      if (ss.find(eulerIn[tmp]) == ss.end()) {
        pq.push({dist[tmp], tmp});
        ss.insert(eulerIn[tmp]);
      }
    }

    printf("%lld\n", ans);
  }

  return 0;
}
0