結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2020-01-03 21:08:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 902 ms / 3,000 ms |
コード長 | 957 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 453,760 KB |
最終ジャッジ日時 | 2024-11-22 19:27:08 |
合計ジャッジ時間 | 8,751 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sysinput = sys.stdin.readlinesys.setrecursionlimit(10 ** 6)def main():N = int(input())edges = [[] for _ in range(N)]path = []for _ in range(N-1):u, v, w = map(int, input().split())u -= 1v -= 1edges[u].append([v,w])edges[v].append([u,w])path.append([u,v,w])subtree_size = [-1] * Ndef dfs(v, p):for nv, w in edges[v]:if nv == p:continuedfs(nv, v)subtree_size[v] = 1for c, w in edges[v]:if c == p:continuesubtree_size[v] += subtree_size[c]dfs(0,-1)ans = 0for u, v, w in path:if subtree_size[u] > subtree_size[v]:ans += 2 * subtree_size[v] * (N - subtree_size[v]) * welse:ans += 2 * subtree_size[u] * (N - subtree_size[u]) * wprint(ans)if __name__ == "__main__":main()