結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2020-03-03 21:43:34 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 409 ms / 3,000 ms |
コード長 | 1,109 bytes |
コンパイル時間 | 182 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 42,112 KB |
最終ジャッジ日時 | 2024-10-13 23:04:12 |
合計ジャッジ時間 | 6,771 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#!/usr/bin/env python3# %%import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesfrom collections import deque# %%N = int(readline())m = map(int, read().split())XY = zip(m, m)# %%G = [[] for _ in range(N + 1)]for x, y in XY:G[x].append(y)G[y].append(x)# %%leaf = [i for i, x in enumerate(G) if len(x) == 1]# %%def dist_from_root():INF = 10 ** 6dist = [INF] * (N + 1)dist[1] = 0q = deque([1])while q:v = q.popleft()for w in G[v]:if dist[w] == INF:dist[w] = dist[v] + 1q.append(w)return dist# %%def dist_from_leaf():INF = 10 ** 6dist = [INF] * (N + 1)q = deque(leaf)for v in leaf:dist[v] = 0while q:v = q.popleft()for w in G[v]:if dist[w] == INF:dist[w] = dist[v] + 1q.append(w)return dist# %%d1, d2 = dist_from_root(), dist_from_leaf()d = (min(x, y) for x, y in zip(d1[1:], d2[1:]))print('\n'.join(map(str, d)))