結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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;
}
//eu-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'e
ll 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;
}//ee'
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);
//ee'
calc2(0, -1);
calc3(0, -1);
cout << ans << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0