結果
問題 | No.898 tri-βutree |
ユーザー | polylogK |
提出日時 | 2019-09-18 01:04:31 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,734 bytes |
コンパイル時間 | 380 ms |
コンパイル使用メモリ | 82,336 KB |
実行使用メモリ | 140,468 KB |
最終ジャッジ日時 | 2024-04-26 08:21:46 |
合計ジャッジ時間 | 25,459 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | AC | 39 ms
52,864 KB |
testcase_02 | AC | 54 ms
63,104 KB |
testcase_03 | AC | 57 ms
63,104 KB |
testcase_04 | AC | 56 ms
62,208 KB |
testcase_05 | AC | 51 ms
62,592 KB |
testcase_06 | AC | 52 ms
62,848 KB |
testcase_07 | AC | 1,445 ms
140,468 KB |
testcase_08 | AC | 1,479 ms
138,684 KB |
testcase_09 | AC | 1,463 ms
138,988 KB |
testcase_10 | AC | 1,494 ms
138,344 KB |
testcase_11 | AC | 1,490 ms
139,252 KB |
testcase_12 | AC | 1,519 ms
138,692 KB |
testcase_13 | AC | 1,500 ms
140,060 KB |
testcase_14 | AC | 1,518 ms
138,212 KB |
testcase_15 | AC | 1,490 ms
140,404 KB |
testcase_16 | AC | 1,496 ms
138,956 KB |
testcase_17 | AC | 1,514 ms
139,180 KB |
testcase_18 | AC | 1,456 ms
139,440 KB |
testcase_19 | AC | 1,448 ms
138,932 KB |
testcase_20 | AC | 1,450 ms
139,248 KB |
testcase_21 | AC | 1,421 ms
139,000 KB |
ソースコード
class lowest_common_ancestor: logN = 20 def __init__(self, N): self.g = [[] for i in range(N)] self.parent = [[-1 for i in range(N)] for i in range(self.logN)] self.depth = [0 for i in range(N)] def add_edge(self, u, v): self.g[u].append(v) self.g[v].append(u) def dfs(self, v, par = -1, d = 0): self.parent[0][v] = par self.depth[v] = d for e in self.g[v]: if e == par: continue self.dfs(e, v, d + 1) def build(self): self.dfs(0) for k in range(self.logN - 1): for i in range(len(self.g)): if self.parent[k][i] == -1: self.parent[k + 1][i] = -1 else: self.parent[k + 1][i] = self.parent[k][self.parent[k][i]] def query(self, u, v): if self.depth[u] > self.depth[v]: u, v = v, u for k in range(self.logN): if (((self.depth[v] - self.depth[u]) >> k) & 1) == 1: v = self.parent[k][v] if u == v: return u for k in range(self.logN - 1, -1, -1): if self.parent[k][u] == self.parent[k][v]: continue u = self.parent[k][u] v = self.parent[k][v] return self.parent[0][u] g = [[]] dist = [] def dfs(v, par): for e in g[v]: if e[0] == par: continue dist[e[0]] = dist[v] + e[1] dfs(e[0], v) lca = lowest_common_ancestor(0) def calc(u, v): c = lca.query(u, v) return dist[u] + dist[v] - 2 * dist[c] if __name__ == "__main__": N = int(input()) g = [[] for i in range(N)] lca = lowest_common_ancestor(N) for i in range(N - 1): a, b, c = map(int, input().split()) g[a].append([b, c]) g[b].append([a, c]) lca.add_edge(a, b) lca.build() dist = [0 for i in range(N)] dfs(0, -1) Q = int(input()) for _ in range(Q): a, b, c = map(int, input().split()) print((calc(a, b) + calc(b, c) + calc(c, a)) >> 1)