Contest Duration: - (local time) (120 minutes) Back to Home

Submission #9925357

Source Code Expand

Copy
```import sys

"""
links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
というグラフ情報から、ダブリングによるLCAを構築。
任意の2頂点のLCAおよび距離を取得できるようにする
"""

self.depths = [-1] * n
self.distances = [-1] * n
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

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 = [set() for _ in range(n)]
for line in lines[:n - 1]:
x, y = map(int, line.split())
x -= 1
y -= 1

for line in lines[n:]:
a, b = map(int, line.split())
a -= 1
b -= 1
print(d + 1)
```

#### Submission Info

Submission Time 2020-02-06 18:30:43+0900 D - 閉路 ikatakos Python (3.4.3) 100 2569 Byte AC 1438 ms 83132 KB

#### Judge Result

Score / Max Score 0 / 0 30 / 30 70 / 70
Status
 AC × 3
 AC × 12
 AC × 27
Set Name Test Cases
Case Name Status Exec Time Memory
subtask0_sample01.txt AC 17 ms 3192 KB
subtask0_sample02.txt AC 18 ms 3192 KB
subtask0_sample03.txt AC 18 ms 3192 KB
subtask1_01.txt AC 506 ms 74940 KB
subtask1_02.txt AC 498 ms 74940 KB
subtask1_03.txt AC 18 ms 3192 KB
subtask1_04.txt AC 18 ms 3192 KB
subtask1_05.txt AC 22 ms 3572 KB
subtask1_06.txt AC 22 ms 3572 KB
subtask1_07.txt AC 519 ms 60864 KB
subtask1_08.txt AC 540 ms 59836 KB
subtask1_09.txt AC 565 ms 60992 KB
subtask1_10.txt AC 594 ms 65084 KB
subtask1_11.txt AC 606 ms 68032 KB
subtask1_12.txt AC 607 ms 65212 KB
subtask2_01.txt AC 1124 ms 83132 KB
subtask2_02.txt AC 1139 ms 83008 KB
subtask2_03.txt AC 466 ms 11072 KB
subtask2_04.txt AC 548 ms 11012 KB
subtask2_05.txt AC 691 ms 12220 KB
subtask2_06.txt AC 666 ms 12268 KB
subtask2_07.txt AC 1159 ms 69692 KB
subtask2_08.txt AC 1210 ms 68544 KB
subtask2_09.txt AC 1335 ms 69696 KB
subtask2_10.txt AC 1438 ms 73148 KB
subtask2_11.txt AC 1436 ms 76040 KB
subtask2_12.txt AC 1433 ms 73148 KB