結果

問題 No.898 tri-βutree
ユーザー 37zigen37zigen
提出日時 2019-10-04 23:06:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,816 bytes
コンパイル時間 713 ms
コンパイル使用メモリ 73,344 KB
実行使用メモリ 40,192 KB
最終ジャッジ日時 2024-10-03 08:29:38
合計ジャッジ時間 12,688 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 371 ms
40,192 KB
testcase_01 AC 3 ms
6,272 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

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))];
    if (ans < 0) ans *= -1;
    std::cout << ans << std::endl;
  }
  
}
0