結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | mkawa2 |
提出日時 | 2021-06-10 17:47:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,060 ms / 2,000 ms |
コード長 | 2,636 bytes |
コンパイル時間 | 399 ms |
コンパイル使用メモリ | 87,036 KB |
実行使用メモリ | 271,120 KB |
最終ジャッジ日時 | 2023-08-08 01:42:16 |
合計ジャッジ時間 | 24,810 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
71,136 KB |
testcase_01 | AC | 1,051 ms
270,612 KB |
testcase_02 | AC | 512 ms
246,680 KB |
testcase_03 | AC | 265 ms
85,812 KB |
testcase_04 | AC | 483 ms
158,932 KB |
testcase_05 | AC | 839 ms
246,468 KB |
testcase_06 | AC | 460 ms
132,040 KB |
testcase_07 | AC | 1,026 ms
249,392 KB |
testcase_08 | AC | 1,045 ms
244,340 KB |
testcase_09 | AC | 1,034 ms
242,616 KB |
testcase_10 | AC | 1,044 ms
242,492 KB |
testcase_11 | AC | 1,027 ms
257,624 KB |
testcase_12 | AC | 1,037 ms
249,376 KB |
testcase_13 | AC | 1,049 ms
257,556 KB |
testcase_14 | AC | 1,016 ms
246,624 KB |
testcase_15 | AC | 344 ms
111,320 KB |
testcase_16 | AC | 611 ms
202,972 KB |
testcase_17 | AC | 457 ms
150,476 KB |
testcase_18 | AC | 402 ms
131,512 KB |
testcase_19 | AC | 559 ms
179,048 KB |
testcase_20 | AC | 1,042 ms
242,740 KB |
testcase_21 | AC | 478 ms
175,120 KB |
testcase_22 | AC | 1,027 ms
249,244 KB |
testcase_23 | AC | 1,000 ms
243,120 KB |
testcase_24 | AC | 1,060 ms
239,424 KB |
testcase_25 | AC | 1,024 ms
271,120 KB |
testcase_26 | AC | 1,038 ms
255,716 KB |
ソースコード
import sys # sys.setrecursionlimit(10**6) int1 = lambda x: int(x)-1 p2D = lambda x: print(*x, sep="\n") def II(): return int(sys.stdin.buffer.readline()) def LI(): return list(map(int, sys.stdin.buffer.readline().split())) def LI1(): return list(map(int1, sys.stdin.buffer.readline().split())) def LLI(rows_number): return [LI() for _ in range(rows_number)] def LLI1(rows_number): return [LI1() for _ in range(rows_number)] def BI(): return sys.stdin.buffer.readline().rstrip() def SI(): return sys.stdin.buffer.readline().rstrip().decode() # dij = [(0, 1), (-1, 0), (0, -1), (1, 0)] # dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)] dij = [(0, 1), (1, 0), (1, 1), (1, -1)] inf = 10**16 md = 998244353 # md = 10**9+7 class SparseTableMin: def __init__(self, aa): w = len(aa) h = w.bit_length() table = [aa]+[[-1]*w for _ in range(h-1)] tablei1 = table[0] for i in range(1, h): tablei = table[i] for j in range(w-(1 << i)+1): rj = j+(1 << (i-1)) tablei[j] = min(tablei1[j], tablei1[rj]) tablei1 = tablei self.table = table def min(self, l, r): i = (r-l).bit_length()-1 tablei = self.table[i] Lmin = tablei[l] Rmin = tablei[r-(1 << i)] if Lmin < Rmin: Rmin = Lmin return Rmin class LCA: def __init__(self, et, depth, first): n = len(depth) self.sp = SparseTableMin([(depth[u], u) for u in et]) self.first = first def get_lca(self, u, v): l, r = self.first[u], self.first[v] if l > r: l, r = r, l return self.sp.min(l, r+1)[1] def EulerTour(to, root=0): n = len(to) et = [] depth = [0]*n first = [0]*n par = [-1]*n toi = [0]*n stack = [root] while stack: u = stack.pop() et.append(u) i = toi[u] if i == 0: first[u] = len(et)-1 if i != len(to[u]): v, c = to[u][i] if v == par[u]: stack.append(u) et.pop() else: depth[v] = depth[u]+1 cost[v] = cost[u]+c par[v] = u stack.append(u) stack.append(v) toi[u] += 1 return et, depth, first n = II() to = [[] for _ in range(n)] for _ in range(n-1): u, v, c = LI1() to[u].append((v, c+1)) to[v].append((u, c+1)) cost = [0]*n et, depth, first = EulerTour(to) lca = LCA(et, depth, first) for _ in range(II()): u, v = LI1() w = lca.get_lca(u, v) print(cost[u]+cost[v]-cost[w]*2)