結果
問題 | No.1333 Squared Sum |
ユーザー | leaf_1415 |
提出日時 | 2021-01-08 22:40:40 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 811 ms / 2,000 ms |
コード長 | 2,456 bytes |
コンパイル時間 | 1,409 ms |
コンパイル使用メモリ | 85,288 KB |
実行使用メモリ | 31,972 KB |
最終ジャッジ日時 | 2023-08-10 10:45:16 |
合計ジャッジ時間 | 18,459 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
8,204 KB |
testcase_01 | AC | 5 ms
8,004 KB |
testcase_02 | AC | 4 ms
8,116 KB |
testcase_03 | AC | 566 ms
19,184 KB |
testcase_04 | AC | 579 ms
19,192 KB |
testcase_05 | AC | 586 ms
19,468 KB |
testcase_06 | AC | 575 ms
19,264 KB |
testcase_07 | AC | 559 ms
19,184 KB |
testcase_08 | AC | 567 ms
19,456 KB |
testcase_09 | AC | 571 ms
19,184 KB |
testcase_10 | AC | 560 ms
19,220 KB |
testcase_11 | AC | 564 ms
19,200 KB |
testcase_12 | AC | 554 ms
19,144 KB |
testcase_13 | AC | 574 ms
31,884 KB |
testcase_14 | AC | 788 ms
25,744 KB |
testcase_15 | AC | 798 ms
30,572 KB |
testcase_16 | AC | 4 ms
8,044 KB |
testcase_17 | AC | 4 ms
8,032 KB |
testcase_18 | AC | 4 ms
8,316 KB |
testcase_19 | AC | 5 ms
8,056 KB |
testcase_20 | AC | 5 ms
8,032 KB |
testcase_21 | AC | 4 ms
8,044 KB |
testcase_22 | AC | 5 ms
8,332 KB |
testcase_23 | AC | 4 ms
8,040 KB |
testcase_24 | AC | 4 ms
8,044 KB |
testcase_25 | AC | 4 ms
8,016 KB |
testcase_26 | AC | 808 ms
31,648 KB |
testcase_27 | AC | 800 ms
26,100 KB |
testcase_28 | AC | 811 ms
31,780 KB |
testcase_29 | AC | 564 ms
31,972 KB |
testcase_30 | AC | 183 ms
12,672 KB |
testcase_31 | AC | 94 ms
10,668 KB |
testcase_32 | AC | 280 ms
14,940 KB |
testcase_33 | AC | 211 ms
13,548 KB |
testcase_34 | AC | 424 ms
17,012 KB |
testcase_35 | AC | 287 ms
14,940 KB |
testcase_36 | AC | 150 ms
12,080 KB |
testcase_37 | AC | 156 ms
12,220 KB |
testcase_38 | AC | 194 ms
12,928 KB |
testcase_39 | AC | 341 ms
16,020 KB |
testcase_40 | AC | 271 ms
18,324 KB |
testcase_41 | AC | 251 ms
18,240 KB |
testcase_42 | AC | 258 ms
18,448 KB |
testcase_43 | AC | 231 ms
18,188 KB |
ソースコード
#include <iostream> #include <cstdio> #include <cmath> #include <ctime> #include <cstdlib> #include <cassert> #include <vector> #include <list> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <string> #include <algorithm> #include <utility> #include <complex> #define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(),(x).end() #define inf 1e18 #define mod 1000000007 using namespace std; typedef long long llint; typedef long long ll; typedef pair<llint, llint> P; struct edge{ ll to, cost; edge(){} edge(ll a, ll b){ to = a, cost = b; } }; int n; vector<edge> G[200005]; int size[200005]; bool used[200005]; int sizedfs(int v, int pre) { int ret = 1; for(int i = 0; i < G[v].size(); i++){ if(G[v][i].to == pre) continue; if(used[G[v][i].to]) continue; ret += sizedfs(G[v][i].to, v); } return size[v] = ret; } int centdfs(int v, int pre, int sz) { for(int i = 0; i < G[v].size(); i++){ if(G[v][i].to == pre) continue; if(used[G[v][i].to]) continue; if(size[G[v][i].to] > sz/2) return centdfs(G[v][i].to, v, sz); } return v; } ll ans = 0; ll num, sum, sum2; ll gnum, gsum, gsum2; void dfs(int v, int p, ll d) { num++, sum += d, sum2 += d*d%mod; for(auto e : G[v]){ ll u = e.to; if(u == p || used[u]) continue; dfs(u, v, (d+e.cost)%mod); } } void solve(int v) { sizedfs(v, -1); v = centdfs(v, -1, size[v]); gnum = gsum = gsum2 = 0; for(auto e : G[v]){ ll u = e.to; if(used[u]) continue; num = sum = sum2 = 0; dfs(u, v, e.cost); sum %= mod, sum2 %= mod; gnum += num, (gsum += sum) %= mod, (gsum2 += sum2) %= mod; ans += mod - num * sum2 * 2 % mod, ans %= mod; ans += mod - sum * sum * 2 % mod, ans %= mod; } //cout << ans << endl; //cout << gnum << " " << gsum << " " << gsum2 << endl; ans += gnum * gsum2 * 2 % mod, ans %= mod; ans += gsum * gsum * 2 % mod, ans %= mod; ans += 2 * gsum2 % mod, ans %= mod; //cout << v << " " << ans << endl; used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(used[G[v][i].to]) continue; solve(G[v][i].to); } } int main(void) { cin >> n; llint u, v, w; for(int i = 0; i < n-1; i++){ cin >> u >> v >> w; G[u].push_back(edge(v, w)); G[v].push_back(edge(u, w)); } solve(1); ans *= (mod+1)/2, ans %= mod; cout << ans << endl; return 0; }