結果
問題 | No.277 根掘り葉掘り |
ユーザー |
|
提出日時 | 2015-09-05 01:48:23 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 1,114 ms / 3,000 ms |
コード長 | 713 bytes |
コンパイル時間 | 525 ms |
コンパイル使用メモリ | 6,784 KB |
実行使用メモリ | 145,736 KB |
最終ジャッジ日時 | 2024-07-19 03:33:10 |
合計ジャッジ時間 | 10,171 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#!/usr/bin/pythonfrom collections import defaultdictimport resource, sysif sys.version_info[0]>=3: raw_input=inputresource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))sys.setrecursionlimit(10**6)def dfs(n,d,z):r=Nonefor e in H[n]:if e not in z:z[e]=1if r is None: r=1<<29x=dfs(e,d+1,z)r=min(r,x+1)del z[e]if r is None: r=0R[n]=min(r,d)L[n]=rreturn rdef dfs2(n,d,z):for e in H[n]:if e not in z:z[e]=1dfs2(e,min(d,L[n])+1,z)del z[e]R[n]=min(R[n],d)n=int(raw_input())H=defaultdict(list)R={}L={}for _ in range(n-1):x,y=map(int,raw_input().split())H[x].append(y)H[y].append(x)dfs(1,0,{1:1})dfs2(1,0,{1:1})for i in range(1,n+1):print(R[i])