結果
問題 | No.872 All Tree Path |
ユーザー | kept1994 |
提出日時 | 2021-08-31 12:57:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 844 ms / 3,000 ms |
コード長 | 1,774 bytes |
コンパイル時間 | 481 ms |
コンパイル使用メモリ | 87,064 KB |
実行使用メモリ | 385,644 KB |
最終ジャッジ日時 | 2023-08-16 17:48:44 |
合計ジャッジ時間 | 8,959 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 682 ms
127,548 KB |
testcase_01 | AC | 665 ms
125,492 KB |
testcase_02 | AC | 668 ms
129,344 KB |
testcase_03 | AC | 844 ms
385,644 KB |
testcase_04 | AC | 74 ms
71,360 KB |
testcase_05 | AC | 679 ms
125,724 KB |
testcase_06 | AC | 695 ms
127,088 KB |
testcase_07 | AC | 673 ms
126,632 KB |
testcase_08 | AC | 172 ms
84,404 KB |
testcase_09 | AC | 172 ms
84,744 KB |
testcase_10 | AC | 174 ms
85,208 KB |
testcase_11 | AC | 177 ms
84,260 KB |
testcase_12 | AC | 170 ms
84,096 KB |
testcase_13 | AC | 75 ms
71,396 KB |
testcase_14 | AC | 74 ms
71,272 KB |
testcase_15 | AC | 74 ms
71,540 KB |
testcase_16 | AC | 73 ms
71,112 KB |
testcase_17 | AC | 72 ms
71,396 KB |
testcase_18 | AC | 73 ms
71,412 KB |
testcase_19 | AC | 74 ms
71,580 KB |
ソースコード
#!/usr/bin/env python3 import sys def main(): sys.setrecursionlimit(10 ** 9) ans = 0 N = int(input()) class DFS(): def __init__(self, N: int) -> None: self.nodes = N # 頂点数 self.G = [[] for _ in range(N)] # グラフ self.seen = [False] * N # 各ノードが訪問済みかどうかのフラグ self.firstOrder = [] # ノードの行きがけ順(0-index) self.lastOrder = [] # ノードの帰りがけ順(0-index) # 辺の追加 def addEdge(self, fromNode: int, toNode: int, cost: int, bothDirection: bool): self.G[fromNode].append((toNode, cost)) if bothDirection: self.G[toNode].append((fromNode, cost)) # DFS def build(self, now: int, pre:int): sum = 0 nonlocal ans # ----- ノードに到着した時の処理 self.firstOrder.append(now) self.seen[now] = True # ----- 隣接する各ノードへの移動処理 for next in self.G[now]: if self.seen[next[0]]: continue sum += self.build(next[0], now) # ----- ノードから戻る時の処理 # self.lastOrder.append(now) sum += 1 for t, c in self.G[now]: if t == pre: ans += sum * (self.nodes - sum) * c return sum d = DFS(N) for _ in range(N - 1): u, v, w = map(int, input().split()) d.addEdge(u - 1, v - 1, w, bothDirection=True) d.build(0, -1) print(ans * 2) if __name__ == '__main__': main()