結果
問題 | No.1333 Squared Sum |
ユーザー |
![]() |
提出日時 | 2021-01-08 22:40:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 806 ms / 2,000 ms |
コード長 | 2,456 bytes |
コンパイル時間 | 827 ms |
コンパイル使用メモリ | 85,736 KB |
実行使用メモリ | 35,072 KB |
最終ジャッジ日時 | 2024-11-16 13:59:02 |
合計ジャッジ時間 | 16,541 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#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 1000000007using 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;}