結果
問題 | No.872 All Tree Path |
ユーザー |
👑 ![]() |
提出日時 | 2020-11-13 03:38:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 532 ms / 3,000 ms |
コード長 | 784 bytes |
コンパイル時間 | 230 ms |
コンパイル使用メモリ | 82,408 KB |
実行使用メモリ | 137,288 KB |
最終ジャッジ日時 | 2024-07-22 19:50:49 |
合計ジャッジ時間 | 6,213 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sysfrom collections import dequeinput=sys.stdin.readlineN=int(input())E=[[] for _ in range(N+1)]Edge=[0]*(N-1)for i in range(N-1):u,v,w=map(int,input().split())E[u].append(v)E[v].append(u)Edge[i]=(u,v,w)root=1Depth=[-1]*(N+1)Depth[root]=0Parent=[-1]*(N+1)Parent[root]=0Q=deque([root])F=[[] for _ in range(N)]F[0]=[root]while Q:v=Q.popleft()for u in E[v]:if Depth[u]==-1:Depth[u]=Depth[v]+1Parent[u]=vQ.append(u)F[Depth[u]].append(u)Descend=[1]*(N+1)for G in F[::-1]:for x in G:if x!=root:Descend[Parent[x]]+=Descend[x]X=0for (u,v,w) in Edge:if Depth[u]>Depth[v]:u,v=v,uX+=w*Descend[v]*(N-Descend[v])print(2*X)