結果
問題 | No.277 根掘り葉掘り |
ユーザー |
![]() |
提出日時 | 2020-06-23 00:12:31 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,246 ms / 3,000 ms |
コード長 | 1,568 bytes |
コンパイル時間 | 81 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 38,016 KB |
最終ジャッジ日時 | 2024-07-03 19:03:12 |
合計ジャッジ時間 | 13,937 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sysinput=lambda: sys.stdin.readline().rstrip()n=int(input())edge=[[] for i in range(n)]for i in range(n-1):a,b=map(int,input().split())edge[a-1].append(b-1)edge[b-1].append(a-1)Ans=[]inf=10**6#親と入次数を求めるPar=[inf]*nPar[0]=-1Deg=[0]*nDeg[0]=0Chk=[0]while Chk:c=Chk.pop()for next in edge[c]:if Par[next]==inf:Par[next]=cDeg[next]+=1Chk.append(next)#トポソするfrom collections import dequeTS=list(v for v in range(n) if Deg[v]==0)D=deque(TS)while D:v=D.popleft()for t in edge[v]:if t!=Par[v]:Deg[t]-=1if Deg[t]==0:D.append(t)TS.append(t)#子の情報を吸い上げる。自分自身も含めた形の、自身を根とする部分木での最大値。C=[inf]*nfor i in reversed(range(n)):v=TS[i]if C[v]==inf:C[v]=0C[Par[v]]=min(C[Par[v]],C[v]+1)#親の情報を渡していく。ここでは自身を含まない。親を含めて親より上の部分木の最大値。D=[inf]*nD[0]=0for i in range(n):v=TS[i] #vの情報を子に渡すif Par[v]==-1:continueelse:D[v]=min(D[v],D[Par[v]]+1)ML=[]EG=[]for g in edge[v]:if g!=Par[v]:EG.append(g)ML.append(C[g])MR=ML[::-1]MML=[inf]for ml in ML:MML.append(min(MML[-1],ml))MMR=[inf]for mr in MR:MMR.append(min(MMR[-1],mr))ng=len(EG)for i,g in enumerate(EG):ming=min(MML[i],MMR[ng-i-1])D[g]=min(D[g],ming+2)for i in range(n):print(min(C[i],D[i]))