結果
問題 | No.1333 Squared Sum |
ユーザー |
![]() |
提出日時 | 2021-01-08 23:23:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,850 bytes |
コンパイル時間 | 2,245 ms |
コンパイル使用メモリ | 198,272 KB |
最終ジャッジ日時 | 2025-01-17 14:42:17 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 WA * 35 |
ソースコード
// https://atcoder.jp/contests/otemae2019/submissions/6651746#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll mod = 1000000007;int N;vector<pair<int, int>> G[500000];ll ans = 0;int subnum[500000];int calc_subnum(int v, int from) {int ret = 1;for (int i = 0; i < G[v].size(); i++){int to = G[v][i].second;if (to == from)continue;ret += calc_subnum(to, v);}return subnum[v] = ret;}//eを通るu-v pathの個数void calc1(int v, int from, int l) {ans += (ll)subnum[v] * (N - subnum[v]) % mod * l % mod * l;ans %= mod;for (int i = 0; i < G[v].size(); i++) {int to = G[v][i].second;if (to == from)continue;calc1(to, v, G[v][i].first);}}//根とe'の間にell calc2(int v, int from) {ll ret = 0;for (int i = 0; i < G[v].size(); i++) {int to = G[v][i].second;if (to == from)continue;ll next = calc2(to, v);ans += next * (N - subnum[to]) % mod * G[v][i].first; ans %= mod;ret += next; ret += subnum[to] * (ll)G[v][i].first; ret %= mod;}return ret;}//eとe'がバラバラll calc3(int v, int from) {ll ret = 0;vector<ll> x;for (int i = 0; i < G[v].size(); i++) {int to = G[v][i].second;if (to == from)continue;ll next = calc3(to, v) + subnum[to] * (ll)G[v][i].first;x.push_back(next); ret += next; ret %= mod;}ll sum = 0;for (int i = 0; i < x.size(); i++) {sum += x[i];}sum %= mod;for (int i = 0; i < x.size(); i++) {ans += x[i] * (sum - x[i] + mod); ans %= mod;}return ret;}int main() {cin >> N;//入力for (int i = 0; i < N - 1; i++) {int A, B, C; cin >> A >> B >> C; A--; B--;G[A].push_back({C, B});G[B].push_back({C, A});}calc_subnum(0, -1);calc1(0, -1, 0);calc2(0, -1);//eとe'の上下を入れ替えてもう一度calc2(0, -1);calc3(0, -1);cout << ans << endl;return 0;}