結果
問題 | 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 syssys.setrecursionlimit(1000000)def dfs(i, d):R[i] = dused[i] = Trueif len(tree[i]) > 0:mn = 1e9for j in tree[i]:if not used[j]:mn = min(mn, dfs(j, d + 1))L[i] = mnL[i] = 0 if mn == 1e9 else mnreturn L[i] + 1def dfs2(i, d):used[i] = Trueif d < L[i]:L[i] = delse: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 -= 1y -= 1tree[x].append(y)tree[y].append(x)R, L = [0] * N, [1e9] * Nused = [False] * Ndfs(0, 0)used = [False] * Ndfs2(0, L[0])for i in xrange(N):print min(R[i], L[i])