結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2020-12-26 17:45:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 323 ms / 3,000 ms |
コード長 | 681 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 116,152 KB |
最終ジャッジ日時 | 2024-09-24 20:21:35 |
合計ジャッジ時間 | 5,694 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
n = int(input())g = [[] for _ in range(n)]for i in range(n-1):a,b = [int(i) for i in input().split()]g[a-1].append(b-1)g[b-1].append(a-1)order = []st = [0]parent = [-1]*nL = [0]*nwhile st:v = st.pop()order.append(v)for c in g[v]:if c != parent[v]:st.append(c)parent[c] = vL[c] = L[v]+1from collections import dequeq = deque()R = [-1]*nfor i in range(1,n):if len(g[i]) == 1:q.append(i)R[i] = 0while q:v = q.popleft()for c in g[v]:if R[c] == -1:R[c] = R[v]+1q.append(c)print(*(min(li,ri) for li,ri in zip(L,R)),sep="\n")