結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2020-04-09 09:22:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 764 ms / 3,000 ms |
コード長 | 607 bytes |
コンパイル時間 | 242 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 178,400 KB |
最終ジャッジ日時 | 2024-07-21 07:23:08 |
合計ジャッジ時間 | 9,222 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sysinput = sys.stdin.readlinen = int(input())g = [[] for _ in range(n)]d = {}for i in range(n-1):u, v, w = map(int, input().split())u, v = u-1, v-1d[(u, v)] = wd[(v, u)] = wg[u].append(v)g[v].append(u)s = []visit = [-1]*ns.append(0)order = []par = [-1]*nwhile s:v = s.pop()order.append(v)for u in g[v]:if u == par[v]:continuepar[u] = vs.append(u)ans = 0c = [1]*norder.reverse()for v in order:if par[v] != -1:ans += (n-c[v])*c[v]*d[(v, par[v])]c[par[v]] += c[v]print(ans*2)