結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2015-09-04 23:59:28 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 1,196 ms / 3,000 ms |
コード長 | 796 bytes |
コンパイル時間 | 649 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 117,504 KB |
最終ジャッジ日時 | 2024-07-19 02:32:29 |
合計ジャッジ時間 | 9,940 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sys sys.setrecursionlimit(1000000) def dfs(i, d): R[i] = d used[i] = True if len(tree[i]) > 0: mn = 1e9 for j in tree[i]: if not used[j]: mn = min(mn, dfs(j, d + 1)) L[i] = mn L[i] = 0 if mn == 1e9 else mn return L[i] + 1 def dfs2(i, d): used[i] = True if d < L[i]: L[i] = d else: d = L[i] for j in tree[i]: if not used[j]: dfs2(j, d + 1) N = int(raw_input()) tree = [[] for i in xrange(N)] for loop in xrange(N - 1): x, y = map(int, raw_input().split()) x -= 1 y -= 1 tree[x].append(y) tree[y].append(x) R, L = [0] * N, [1e9] * N used = [False] * N dfs(0, 0) used = [False] * N dfs2(0, L[0]) for i in xrange(N): print min(R[i], L[i])