結果
問題 | No.898 tri-βutree |
ユーザー | kohei2019 |
提出日時 | 2022-08-01 23:15:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,101 ms / 4,000 ms |
コード長 | 2,937 bytes |
コンパイル時間 | 279 ms |
コンパイル使用メモリ | 87,172 KB |
実行使用メモリ | 141,188 KB |
最終ジャッジ日時 | 2023-09-29 20:02:46 |
合計ジャッジ時間 | 19,536 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 454 ms
120,420 KB |
testcase_01 | AC | 71 ms
71,000 KB |
testcase_02 | AC | 80 ms
75,648 KB |
testcase_03 | AC | 81 ms
75,540 KB |
testcase_04 | AC | 80 ms
75,732 KB |
testcase_05 | AC | 80 ms
75,540 KB |
testcase_06 | AC | 82 ms
75,736 KB |
testcase_07 | AC | 940 ms
113,992 KB |
testcase_08 | AC | 2,101 ms
141,188 KB |
testcase_09 | AC | 900 ms
113,492 KB |
testcase_10 | AC | 843 ms
113,712 KB |
testcase_11 | AC | 838 ms
113,748 KB |
testcase_12 | AC | 909 ms
114,456 KB |
testcase_13 | AC | 891 ms
114,772 KB |
testcase_14 | AC | 897 ms
115,724 KB |
testcase_15 | AC | 828 ms
114,208 KB |
testcase_16 | AC | 791 ms
113,980 KB |
testcase_17 | AC | 1,645 ms
132,408 KB |
testcase_18 | AC | 859 ms
113,176 KB |
testcase_19 | AC | 867 ms
115,128 KB |
testcase_20 | AC | 906 ms
113,436 KB |
testcase_21 | AC | 905 ms
113,684 KB |
ソースコード
#最小共通祖先 #ダブリング class LcaDoubling: """ links[v] = { (u, w), (u, w), ... } (u:隣接頂点, w:辺の重み) というグラフ情報から、ダブリングによるLCAを構築。 任意の2頂点のLCAおよび距離を取得できるようにする """ def __init__(self, n, links, root=0): self.depths = [-1] * n self.distances = [-1] * n prev_ancestors = self._init_dfs(n, links, root) self.ancestors = [prev_ancestors] max_depth = max(self.depths) d = 1 while d < max_depth: next_ancestors = [prev_ancestors[p] for p in prev_ancestors] self.ancestors.append(next_ancestors) d <<= 1 prev_ancestors = next_ancestors def _init_dfs(self, n, links, root): q = [(root, -1, 0, 0)] direct_ancestors = [-1] * (n + 1) # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1 while q: v, p, dep, dist = q.pop() direct_ancestors[v] = p self.depths[v] = dep self.distances[v] = dist q.extend((u, v, dep + 1, dist + w) for u, w in links[v] if u != p) return direct_ancestors def get_lca(self, u, v): du, dv = self.depths[u], self.depths[v] if du > dv: u, v = v, u du, dv = dv, du tu = u tv = self.upstream(v, dv - du) if u == tv: return u for k in range(du.bit_length() - 1, -1, -1): mu = self.ancestors[k][tu] mv = self.ancestors[k][tv] if mu != mv: tu = mu tv = mv lca = self.ancestors[0][tu] assert lca == self.ancestors[0][tv] return lca def get_distance(self, u, v): lca = self.get_lca(u, v) return self.distances[u] + self.distances[v] - 2 * self.distances[lca] def upstream(self, v, k): i = 0 while k: if k & 1: v = self.ancestors[i][v] k >>= 1 i += 1 return v N = int(input()) links = [[] for i in range(N)] for i in range(N-1): u,v,w = map(int,input().split()) links[u].append((v,w)) links[v].append((u,w)) LCA = LcaDoubling(N, links) Q = int(input()) ans = [] for i in range(Q): x,y,z = map(int,input().split()) a = LCA.get_lca(x, y) b = LCA.get_lca(y, z) c = LCA.get_lca(z, x) if a == b == c: dist = LCA.get_distance(0,x)+LCA.get_distance(0,y)+LCA.get_distance(0,z)-3*LCA.get_distance(0,a) else: l = [a,b,c] l.sort() r2 = l[1] for i in range(3): if l[i] != r2: r1 = l[i] dist = LCA.get_distance(0,x)+LCA.get_distance(0,y)+LCA.get_distance(0,z)-2*LCA.get_distance(0,r2)-LCA.get_distance(0,r1) ans.append(dist) print(*ans,sep='\n')