結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2019-12-07 22:42:47 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 916 ms / 3,000 ms |
コード長 | 1,254 bytes |
コンパイル時間 | 200 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 53,760 KB |
最終ジャッジ日時 | 2024-12-26 13:48:46 |
合計ジャッジ時間 | 12,167 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)from collections import dequedef bfs1():q = deque([0])dist = [-1]*Ndist[0] = 0while q:v = q.popleft()for nv in adj_list[v]:if dist[nv]==-1:dist[nv] = dist[v]+1q.append(nv)return distdef dfs(v, p):is_leaf = Trueres = 10**18for nv in adj_list[v]:if nv==p:continueis_leaf = Falseres = min(res, dfs(nv, v)+1)if is_leaf:res = 0from_leaf[v] = resreturn resdef bfs2():q = deque([0])visited = [-1]*Nvisited[0] = 1while q:v = q.popleft()for nv in adj_list[v]:if visited[nv]==-1:visited[nv] = 1from_leaf[nv] = min(from_leaf[nv], from_leaf[v]+1)q.append(nv)N = int(input())adj_list = [[] for _ in range(N)]for _ in range(N-1):xi, yi = map(int, input().split())adj_list[xi-1].append(yi-1)adj_list[yi-1].append(xi-1)from_root = bfs1()from_leaf = [-1]*Ndfs(0, -1)bfs2()for i in range(N):print(min(from_root[i], from_leaf[i]))