結果
問題 | No.872 All Tree Path |
ユーザー |
![]() |
提出日時 | 2020-08-31 01:14:39 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,707 ms / 3,000 ms |
コード長 | 1,014 bytes |
コンパイル時間 | 3,788 ms |
コンパイル使用メモリ | 79,308 KB |
実行使用メモリ | 134,636 KB |
最終ジャッジ日時 | 2024-12-26 02:53:51 |
合計ジャッジ時間 | 26,855 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import java.util.*;public class Main {static long total = 0;static int n;static ArrayList<HashMap<Integer, Integer>> graph;public static void main (String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();graph = new ArrayList<>();for (int i = 0; i < n; i++) {graph.add(new HashMap<>());}for (int i = 0; i < n - 1; i++) {int a = sc.nextInt() - 1;int b = sc.nextInt() - 1;int c = sc.nextInt();graph.get(a).put(b, c);graph.get(b).put(a, c);}for (int x : graph.get(0).keySet()) {calc(x, 0);}System.out.println(total);}static int calc(int idx, int parent) {int sum = 1;for (int x : graph.get(idx).keySet()) {if (x == parent) {continue;}sum += calc(x, idx);}total += graph.get(idx).get(parent) * (long)(n - sum) * sum * 2;return sum;}}