結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | brthyyjp |
提出日時 | 2020-09-13 03:11:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,384 ms / 2,000 ms |
コード長 | 3,787 bytes |
コンパイル時間 | 513 ms |
コンパイル使用メモリ | 82,204 KB |
実行使用メモリ | 210,872 KB |
最終ジャッジ日時 | 2024-04-25 19:29:46 |
合計ジャッジ時間 | 26,523 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
55,460 KB |
testcase_01 | AC | 1,104 ms
200,320 KB |
testcase_02 | AC | 282 ms
210,872 KB |
testcase_03 | AC | 312 ms
85,712 KB |
testcase_04 | AC | 498 ms
131,160 KB |
testcase_05 | AC | 828 ms
175,228 KB |
testcase_06 | AC | 524 ms
117,268 KB |
testcase_07 | AC | 1,123 ms
199,732 KB |
testcase_08 | AC | 1,199 ms
184,164 KB |
testcase_09 | AC | 1,120 ms
183,540 KB |
testcase_10 | AC | 1,119 ms
200,932 KB |
testcase_11 | AC | 1,182 ms
186,056 KB |
testcase_12 | AC | 1,272 ms
189,240 KB |
testcase_13 | AC | 1,149 ms
183,072 KB |
testcase_14 | AC | 1,124 ms
186,612 KB |
testcase_15 | AC | 360 ms
109,956 KB |
testcase_16 | AC | 521 ms
190,396 KB |
testcase_17 | AC | 434 ms
142,548 KB |
testcase_18 | AC | 417 ms
128,252 KB |
testcase_19 | AC | 501 ms
167,268 KB |
testcase_20 | AC | 1,384 ms
186,432 KB |
testcase_21 | AC | 441 ms
147,556 KB |
testcase_22 | AC | 1,173 ms
184,088 KB |
testcase_23 | AC | 1,132 ms
200,332 KB |
testcase_24 | AC | 1,120 ms
185,964 KB |
testcase_25 | AC | 1,140 ms
200,548 KB |
testcase_26 | AC | 1,120 ms
185,560 KB |
ソースコード
class SegTree: def __init__(self, init_val, ide_ele, segfunc): self.n = len(init_val) self.num = 2**(self.n-1).bit_length() self.ide_ele = ide_ele self.segfunc = segfunc self.seg = [ide_ele]*2*self.num # set_val for i in range(self.n): self.seg[i+self.num] = init_val[i] # built for i in range(self.num-1, 0, -1): self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1]) def update(self, k, x): k += self.num self.seg[k] = x while k: k = k >> 1 self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1]) def query(self, l, r): if r <= l: return self.ide_ele l += self.num r += self.num res = self.ide_ele while l < r: if r & 1: r -= 1 res = self.segfunc(res, self.seg[r]) if l & 1: res = self.segfunc(res, self.seg[l]) l += 1 l = l >> 1 r = r >> 1 return res def segfunc(x, y): if x <= y: return x else: return y ide_ele = 10**18 class LCA: def __init__(self, g, root): # g: adjacency list # root self.n = len(g) self.root = root s = [self.root] self.parent = [-1]*self.n self.child = [[] for _ in range(self.n)] visit = [-1]*self.n visit[self.root] = 0 while s: v = s.pop() for u in g[v]: if visit[u] == -1: self.parent[u] = v self.child[v].append(u) visit[u] = 0 s.append(u) # Euler tour tank = [self.root] self.eulerTour = [] self.left = [0]*self.n self.right = [-1]*self.n self.depth = [-1]*self.n eulerNum = -1 de = -1 while tank: v = tank.pop() if v >= 0: eulerNum += 1 self.eulerTour.append(v) self.left[v] = eulerNum self.right[v] = eulerNum tank.append(~v) de += 1 self.depth[v] = de for u in self.child[v]: tank.append(u) else: de -= 1 if ~v != self.root: self.eulerTour.append(self.parent[~v]) eulerNum += 1 self.right[self.parent[~v]] = eulerNum #A = [self.depth[e] for e in self.eulerTour] A = [0]*(2*self.n-1) for i, e in enumerate(self.eulerTour): A[i] = self.depth[e]*(2*self.n-1)+i self.seg = SegTree(A, ide_ele, segfunc) def getLCA(self, u, v): # u, v: 0-indexed p = min(self.left[u], self.left[v]) q = max(self.right[u], self.left[v])+1 m = self.seg.query(p, q) return self.eulerTour[m%(2*self.n-1)] import sys import io, os #input = sys.stdin.buffer.readline input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline n = int(input()) g = [[] for _ in range(n)] C = [[] for _ in range(n)] for i in range(n-1): a, b, c = map(int, input().split()) a, b = a-1, b-1 g[a].append(b) g[b].append(a) C[a].append((c, b)) C[b].append((c, a)) from collections import deque q = deque([]) q.append(0) dist = [-1]*n dist[0] = 0 while q: v = q.popleft() for c, u in C[v]: if dist[u] == -1: dist[u] = dist[v]+c q.append(u) lca = LCA(g, 0) q = int(input()) for i in range(q): s, t = map(int, input().split()) s, t = s-1, t-1 l = lca.getLCA(s, t) ans = dist[s]+dist[t]-2*dist[l] print(ans)