結果

問題 No.898 tri-βutree
ユーザー MayimgMayimg
提出日時 2019-10-06 13:28:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 262 ms / 4,000 ms
コード長 2,787 bytes
コンパイル時間 2,525 ms
コンパイル使用メモリ 213,644 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-11-08 22:52:59
合計ジャッジ時間 8,583 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 109 ms
30,592 KB
testcase_01 AC 5 ms
8,064 KB
testcase_02 AC 6 ms
8,192 KB
testcase_03 AC 6 ms
8,064 KB
testcase_04 AC 6 ms
8,064 KB
testcase_05 AC 6 ms
8,064 KB
testcase_06 AC 6 ms
8,192 KB
testcase_07 AC 261 ms
28,416 KB
testcase_08 AC 261 ms
28,416 KB
testcase_09 AC 247 ms
28,416 KB
testcase_10 AC 241 ms
28,416 KB
testcase_11 AC 248 ms
28,416 KB
testcase_12 AC 246 ms
28,416 KB
testcase_13 AC 247 ms
28,416 KB
testcase_14 AC 248 ms
28,416 KB
testcase_15 AC 258 ms
28,544 KB
testcase_16 AC 255 ms
28,416 KB
testcase_17 AC 255 ms
28,416 KB
testcase_18 AC 261 ms
28,416 KB
testcase_19 AC 255 ms
28,416 KB
testcase_20 AC 262 ms
28,416 KB
testcase_21 AC 255 ms
28,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
class LowestCommonAncestor {
private:
  static const int MAX_SIZE = 30;
  vector<vector<int>> graph;
  vector<int> parent[MAX_SIZE];
  vector<int> depth;
  int bit_length;
  void copy(const vector<int> g[], int siz) { 
    graph.resize(siz);
    for (int i = 0; i < siz; ++i) for (int j : g[i]) graph[i].push_back(j);
  }
  void copy(const vector<vector<int>>& g, int siz = -1) {
    if (siz < 0) siz = (int) g.size();
    graph.resize(siz);
    for (int i = 0; i < siz; ++i) for (int j : g[i]) graph[i].push_back(j);
  }
  void initialize() {
    int siz = (int) graph.size();
    int root = 0;
    bit_length = 1;
    while ((1 << bit_length) < siz) ++bit_length;
    for (int i = 0; i < bit_length; ++i) parent[i].resize(siz);
    depth.assign(siz, -1);
    dfs(root, -1, 0);
    for (int i = 0; i < bit_length- 1; ++i) {
      for (int v = 0; v < siz; ++v) {
        if (depth[v] == -1) continue;
        if (parent[i][v] < 0) parent[i + 1][v] = -1;
        else parent[i + 1][v] = parent[i][parent[i][v]];
      }
    }
  }
  void dfs(int cur, int par, int d) {
    parent[0][cur] = par;
    depth[cur] = d;
    for (int child : graph[cur]) if (child != par) dfs(child, cur, d + 1);
  }
public:
  LowestCommonAncestor() {}
  LowestCommonAncestor(const vector<vector<int>>& g, int siz = -1) { build(g, siz); }
  LowestCommonAncestor(const vector<int> g[], int siz) { build(g, siz); }
  void build(const vector<int> g[], int siz) { copy(g, siz); initialize(); }
  void build(const vector<vector<int>>& g, int siz = -1) { copy(g, siz); initialize(); }
  int get(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int i = 0; i < bit_length; ++i) if (((depth[v] - depth[u]) >> i) & 1) v = parent[i][v];
    if (u == v) return u;
    for (int i = bit_length - 1; i >= 0; --i) if (parent[i][u] != parent[i][v]) u = parent[i][u], v = parent[i][v];
    return parent[0][u];
  }
};
using LCA = LowestCommonAncestor;
vector<pair<int, int>> g[101010];
vector<int> gg[101010];
long long dist[101010];
void dfs (int cur, int par, long long d) {
  dist[cur] = d;
  for (auto p : g[cur]) {
    if (p.first == par) continue;
    dfs(p.first, cur, d + p.second);
  }
}
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i + 1 < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    gg[u].push_back(v);
    gg[v].push_back(u);
  }
  LCA lca(gg, n);
  dfs (0, -1, 0);
  int q;
  cin >> q;
  while (q--) {
    int x, y, z;
    cin >> x >> y >> z;
    cout << (dist[x] * 2 + dist[y] * 2 + dist[z] * 2 - dist[lca.get(x, y)] * 2 - dist[lca.get(y, z)] * 2 - dist[lca.get(z, x)] * 2) / 2 << '\n';
  } 
  return 0;
}
0