結果
問題 | No.872 All Tree Path |
ユーザー |
|
提出日時 | 2019-09-30 06:58:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 206 ms / 3,000 ms |
コード長 | 953 bytes |
コンパイル時間 | 2,673 ms |
コンパイル使用メモリ | 95,324 KB |
実行使用メモリ | 34,284 KB |
最終ジャッジ日時 | 2024-10-03 05:06:41 |
合計ジャッジ時間 | 5,446 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
#define _USE_MATH_DEFINES#include <cmath>#include <cstdio>#include <vector>#include <iostream>#include <algorithm>#include <string>#include<math.h>#include<iomanip>#include<stdio.h>#include <stdlib.h>#include<stdio.h>#include <queue>#include<map>#include <sstream>#include<set>#include<stack>//#include<bits/stdc++.h>using namespace std;int n;long long ans = 0;vector<vector<pair<int, long long>>>p;vector<long long>s;void df(int cur, int prev, long long d) {for (int i = 0; i < p[cur].size(); i++) {int next = p[cur][i].first;if (next != prev)df(next, cur, p[cur][i].second);}if(prev == -1) return;s[prev] += s[cur];ans += d*s[cur] * (n - s[cur]) * 2;}int main() {cin >> n;p.resize(n);s.resize(n, 1);for (int i = 0; i < n-1; i++) {int a, b, d;cin >> a >> b >> d;a--; b--;p[a].push_back({b,d});p[b].push_back({a,d });}df(0, -1, -1);cout << ans << endl;return 0;}