結果

問題 No.898 tri-βutree
ユーザー 37zigen37zigen
提出日時 2019-10-04 23:29:58
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 678 ms / 4,000 ms
コード長 1,820 bytes
コンパイル時間 1,079 ms
コンパイル使用メモリ 73,344 KB
実行使用メモリ 40,064 KB
最終ジャッジ日時 2024-11-08 22:30:36
合計ジャッジ時間 13,851 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 375 ms
40,064 KB
testcase_01 AC 5 ms
6,144 KB
testcase_02 AC 5 ms
6,144 KB
testcase_03 AC 5 ms
6,144 KB
testcase_04 AC 5 ms
6,144 KB
testcase_05 AC 5 ms
6,144 KB
testcase_06 AC 5 ms
6,144 KB
testcase_07 AC 668 ms
35,840 KB
testcase_08 AC 678 ms
35,840 KB
testcase_09 AC 668 ms
35,840 KB
testcase_10 AC 671 ms
35,840 KB
testcase_11 AC 671 ms
35,840 KB
testcase_12 AC 674 ms
35,840 KB
testcase_13 AC 658 ms
35,712 KB
testcase_14 AC 670 ms
35,840 KB
testcase_15 AC 668 ms
35,840 KB
testcase_16 AC 662 ms
35,840 KB
testcase_17 AC 664 ms
35,840 KB
testcase_18 AC 669 ms
35,712 KB
testcase_19 AC 667 ms
35,840 KB
testcase_20 AC 669 ms
35,840 KB
testcase_21 AC 671 ms
35,840 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <deque>
#include <assert.h>


const int NMAX = 112345;
long long sz[NMAX];
int depth[NMAX];
int up[NMAX][60];
std::vector<std::pair<int, long long>> g[NMAX];

void dfs(int cur, int par) {
  up[cur][0] = par;
  sz[cur] = (par == -1 ? 0 : sz[par]) + sz[cur];
  depth[cur] = (par == -1 ? 0 : depth[par]) + 1;
  for (std::pair<int, long long> p : g[cur]) {
    int dst = p.first;
    long long w = p.second;
    if (dst == par) continue;
    sz[dst] += w;
    dfs(dst, cur);
  }
}

int lca(int u, int v) {
  if (depth[u] != depth[v]) {
    if (depth[u] > depth[v]) {
      u ^= v;
      v ^= u;
      u ^= v;
    }
    int diff = depth[v] - depth[u];
    for (int i = 0; i < 60; ++i) {
      if ((diff & (1LL << i)) > 0) {
        v = up[v][i];
      }
    }
  }
  if (u == v) return u;
  assert(depth[u] == depth[v]);
  assert(u != -1 && v != -1);
  assert(u != v);
  for (int i = 59; i >= 0; --i) {
    if (up[v][i] != up[u][i]) {
      v = up[v][i];
      u = up[u][i];
    }
  }
  assert(u != -1 && v != -1);
  assert(depth[u]  == depth[v]);
  assert(u != v);
  return up[u][0];
}

int main() {

  int N;
  std::cin >> N;
  for (int i = 0; i < N - 1; ++i) {
    int u, v;
    long long w;
    std::cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  dfs(0, -1);
  for (int i = 1; i < 60; ++i) {
    for (int j = 0; j < N; ++j) {
      if (up[j][i - 1] != -1) 
        up[j][i] = up[up[j][i - 1]][i - 1];
      else
        up[j][i] = -1;
    }
  }
  int Q;
  std::cin >> Q;
  for (int i = 0; i < Q; ++i) {
    int x, y, z;
    std::cin >> x >> y >> z;
    long long ans = sz[x] + sz[y] + sz[z] - sz[lca(x, y)] - sz[lca(y, z)] - sz[lca(z, x)] + sz[lca(x, lca(y, z))];
    ans -= sz[lca(x, lca(y, z))];
    std::cout << ans << std::endl;
  }

}
0