結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2017-09-05 22:26:05 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,051 ms / 3,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 101 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 37,564 KB |
最終ジャッジ日時 | 2024-11-06 22:30:14 |
合計ジャッジ時間 | 12,966 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
from collections import dequeINF = float('inf')N = int(input())nodes = [[] for _ in range(N)]for n in range(N-1):x,y = list(map(int, input().split(' ')))x -= 1y -= 1nodes[x].append(y)nodes[y].append(x)# find leavesleaves = []for i in range(N):if len(nodes[i]) == 1 and i != 0:leaves.append(i)# find distance from the rootd1 = [INF] * Nq = deque()q.append((0,-1))d1[0] = 0while 0 < len(q):m,n = q.popleft()for c in nodes[m]:if c != n and d1[c] == INF:d1[c] = min(d1[c], d1[m] + 1)q.append((c,m))# find distance from the leafd2 = [INF] * Nq = deque()for i in leaves:q.append((i,-1))d2[i] = 0while 0 < len(q):m,n = q.popleft()for c in nodes[m]:if c != n and d2[c] == INF:d2[c] = min(d2[c], d2[m] + 1)q.append((c,m))for i in range(N):print(min(d1[i], d2[i]))