結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2022-09-22 00:10:07 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,042 ms / 3,000 ms |
コード長 | 886 bytes |
コンパイル時間 | 262 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 47,616 KB |
最終ジャッジ日時 | 2024-12-22 04:28:27 |
合計ジャッジ時間 | 13,057 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
N=int(input())E=[[] for i in range(N)]for i in range(N-1):x,y=map(int,input().split())x-=1y-=1E[x].append(y)E[y].append(x)ROOT=0QUE=[ROOT]Parent=[-1]*(N+1)Parent[ROOT]=N # ROOTの親を定めておく.Child=[[] for i in range(N+1)]TOP_SORT=[] # トポロジカルソートDEG=[1<<30]*NDEG[0]=0while QUE: # トポロジカルソートと同時に親を見つけるx=QUE.pop()TOP_SORT.append(x)for to in E[x]:if Parent[to]==-1:Parent[to]=xChild[x].append(to)QUE.append(to)DEG[to]=DEG[x]+1DEG2=[1<<30]*Nfor x in TOP_SORT[::-1]:if DEG2[x]==1<<30:DEG2[x]=0if 0<=Parent[x]<N:DEG2[Parent[x]]=min(DEG2[x]+1,DEG2[Parent[x]])for x in TOP_SORT[1:]:DEG2[x]=min(DEG2[x],DEG2[Parent[x]]+1)for i in range(N):print(min(DEG[i],DEG2[i]))