結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2020-05-06 16:35:01 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 1,426 ms / 3,000 ms |
コード長 | 1,672 bytes |
コンパイル時間 | 135 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 125,184 KB |
最終ジャッジ日時 | 2024-06-28 18:14:04 |
合計ジャッジ時間 | 13,490 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
class Tree():def __init__(self, n, edge):self.n = nself.tree = [[] for _ in range(n)]for e in edge:self.tree[e[0] - 1].append((e[1] - 1, e[2]))self.tree[e[1] - 1].append((e[0] - 1, e[2]))def setroot(self, root):self.root = rootself.parent = [None for _ in range(self.n)]self.parent[root] = -1self.depth = [None for _ in range(self.n)]self.depth[root] = 0self.distance = [None for _ in range(self.n)]self.distance[root] = 0self.order = []self.order.append(root)self.cost = [0 for _ in range(self.n)]self.size = [1 for _ in range(self.n)]stack = [root]while stack:node = stack.pop()for adj, cost in self.tree[node]:if self.parent[adj] is None:self.parent[adj] = nodeself.depth[adj] = self.depth[node] + 1self.distance[adj] = self.distance[node] + costself.cost[adj] = costself.order.append(adj)stack.append(adj)for node in self.order[::-1]:for adj, cost in self.tree[node]:if self.parent[node] == adj:continueself.size[node] += self.size[adj]import sysinput = sys.stdin.readlineN = int(input())E = [tuple(map(int, input().split())) for _ in range(N - 1)]tree = Tree(N, E)tree.setroot(0)res = 0for node in range(N):if node == 0:continueres += tree.cost[node] * tree.size[node] * (N - tree.size[node]) * 2print(res)