結果
問題 | No.1333 Squared Sum |
ユーザー |
|
提出日時 | 2021-01-08 23:31:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 523 ms / 2,000 ms |
コード長 | 8,285 bytes |
コンパイル時間 | 2,122 ms |
コンパイル使用メモリ | 142,864 KB |
実行使用メモリ | 99,328 KB |
最終ジャッジ日時 | 2024-11-16 18:27:56 |
合計ジャッジ時間 | 14,752 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#pragma GCC target ("avx")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#define _USE_MATH_DEFINES#include<iostream>#include<string>#include<queue>#include<cmath>#include<map>#include<set>#include<list>#include<iomanip>#include<vector>#include<random>#include<functional>#include<algorithm>#include<stack>#include<cstdio>#include<cstring>#include<bitset>#include<unordered_map>#include<climits>#include<fstream>#include<complex>#include<time.h>#include<cassert>#include<functional>#include<numeric>#include<tuple>using namespace std;using ll = long long;using ld = long double;using H = pair<ll, ll>;using P = pair<ll, H>;using vi = vector<ll>;#define all(a) (a).begin(),(a).end()#define fs first#define sc second#define xx first#define yy second.first#define zz second.second#define Q(i,j,k) mkp(i,mkp(j,k))#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)#define rep(i,n) rng(i, 0, (n))#define mkp make_pair#define vec vector#define pb emplace_back#define siz(a) int(a.size())#define crdcomp(b) sort(all((b)));(b).erase(unique(all((b))),(b).end())#define getidx(b,i) (lower_bound(all(b),(i))-(b).begin())#define ssp(i,n) (i==(ll)(n)-1?"\n":" ")#define ctoi(c) (int)(c-'0')#define itoc(c) (char)(c+'0')#define cyes printf("Yes\n")#define cno printf("No\n")#define cdf(n) for(int quetimes_=(n);quetimes_>0;quetimes_--)#define gcj printf("Case #%lld: ",qq123_+1)#define readv(a,n) a.resize(n,0);rep(i,(n)) a[i]=read()#define found(a,x) (a.find(x)!=a.end())constexpr ll mod = (ll)1e9 + 7;constexpr ll Mod = 998244353;constexpr ld EPS = 1e-10;constexpr ll inf = (ll)3 * 1e18;constexpr int Inf = (ll)15 * 1e8;constexpr int dx[] = { -1,1,0,0 }, dy[] = { 0,0,-1,1 };template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }ll read() { ll u, k = scanf("%lld", &u); return u; }string reads() { string s; cin >> s; return s; }H readh(short g = 0) { H u; int k = scanf("%lld %lld", &u.fs, &u.sc); if (g == 1) u.fs--, u.sc--; if (g == 2) u.fs--; return u; }bool ina(H t, int h, int w) { return 0 <= t.fs && t.fs < h && 0 <= t.sc && t.sc < w; }bool ina(int t, int l, int r) { return l <= t && t < r; }ll gcd(ll i, ll j) { return j ? gcd(j, i % j) : i; }ll ppc(ll x) {int sum = 0; for (int i = 0; i < 60; i++)if ((1ll << i) & x) sum++;return sum;}void fin1() { printf("-1\n"); exit(0); }void fin0() { printf("0\n"); exit(0); }template<typename T>class csum {vec<T> v;public:csum(vec<T>& a) :v(a) { build(); }csum() {}csum(int sz) { init(sz); }void init(int sz) { v = vector<T>(sz + 1, 0); }void init(vec<T>& a) { v = a; build(); }void build() {for (int i = 1; i < v.size(); i++) v[i] += v[i - 1];}void add(int l, int r, T x) {v[l] += x;v[r] -= x;}//[l,r)void add(int t, T x) {v[t] += x;}//[l,r)//[l,r]T a(int l, int r) {if (r < l) return 0;return v[r] - (l == 0 ? 0 : v[l - 1]);}//[l,r)T b(int l, int r) {return a(l, r - 1);}T a(pair<int, int>t) {return a(t.first, t.second);}T b(pair<int, int>t) {return b(t.first, t.second);}T operator[](int x)const {return v[x];}};template<ll mod>class modint {public:ll v;modint(ll v = 0) { s(v % mod + mod); }constexpr static int fn_ = (ll)2e6 + 5;static vector<modint>fact, comp;modint pow(ll x) const {modint b(v), c(1);while (x) {if (x & 1) c *= b;b *= b;x >>= 1;}return c;}inline modint& s(int vv) {v = vv < mod ? vv : vv - mod;return *this;}inline modint inv()const { return pow(mod - 2); }inline modint operator-()const { return modint() - *this; }inline modint& operator+=(const modint b) { return s(v + b.v); }inline modint& operator-=(const modint b) { return s(v + mod - b.v); }inline modint& operator*=(const modint b) { v = v * b.v % mod; return *this; }inline modint& operator/=(const modint b) { v = v * b.inv().v % mod; return *this; }inline modint operator+(const modint& b) const { return modint(v) += b; }inline modint operator-(const modint& b) const { return modint(v) -= b; }inline modint operator*(const modint& b) const { return modint(v) *= b; }inline modint operator/(const modint& b) const { return modint(v) /= b; }friend ostream& operator<<(ostream& os, const modint& m) {return os << m.v;}friend istream& operator>>(istream& is, modint& m) {int x; is >> x; m = modint(x);return is;}bool operator<(const modint& r)const { return v < r.v; }bool operator>(const modint& r)const { return v > r.v; }bool operator<=(const modint& r)const { return v <= r.v; }bool operator>=(const modint& r)const { return v >= r.v; }bool operator==(const modint& r)const { return v == r.v; }bool operator!=(const modint& r)const { return v != r.v; }explicit operator bool()const { return v; }explicit operator int()const { return v; }modint comb(modint k) {if (k > *this) return modint();if (fact.empty()) combinit();if (v >= fn_) {if (k > *this - k) k = *this - k;modint tmp(1);for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);return tmp * comp[k.v];}return fact[v] * comp[k.v] * comp[v - k.v];}//nCkmodint perm(modint k) {if (k > *this) return modint();if (fact.empty()) combinit();if (v >= fn_) {modint tmp(1);for (int i = v; i >= v - k.v + 1; i--) tmp *= modint(i);return tmp;}return fact[v] * comp[v - k.v];}//nPkstatic void combinit() {fact.assign(fn_, modint());fact[0] = 1;for (int i = 1; i < fn_; i++) fact[i] = fact[i - 1] * modint(i);comp.assign(fn_, modint());comp[fn_ - 1] = fact[fn_ - 1].inv();for (int i = fn_ - 2; i >= 0; i--) comp[i] = comp[i + 1] * modint(i + 1);}};using mint = modint<ll(1e9 + 7)>; template<>vec<mint> mint::fact = vec<mint>(); template<>vec<mint> mint::comp = vec<mint>();//--------------------------------------------------------------//--------------------------------------------------------------ll n;vec<H>e[300000];ll cnt[300000];mint dp[300000];signed main() {cin >> n;rep(i, n - 1) {int u, v, w; cin >> u >> v >> w;u--; v--;e[u].pb(H{ v,w });e[v].pb(H{ u,w });}auto dfs = [&](int x, int p, ll cst, auto& dfs) ->pair<ll, mint> {ll sum = 0; mint ret = 0;for (auto g : e[x]) {if (g.fs == p) continue;auto t = dfs(g.fs, x, g.sc, dfs);sum += t.fs;ret += t.sc;}if (x > 0) {cnt[x] = sum + 1;dp[x] = ret;}return mkp(sum + 1, ret + (sum + 1) * cst);};dfs(0, -1, 0, dfs);mint ans = 0;auto dfs2 = [&](int x, int p, ll cst, mint r, auto& dfs2)->void {//とりあえずここを求めるif (x > 0) {ans += mint(cst) * cst *cnt[x] * (n - cnt[x]);ans += (r * cnt[x] + dp[x] * (n - cnt[x]))* cst;}vec<mint> d; vi h;for (auto g : e[x]) {if (g.fs != p) {d.pb(dp[g.fs] + (cnt[g.fs] * g.sc));h.pb(cnt[g.fs]);}else d.pb(0), h.pb(0);}csum<mint>c(d);csum<ll>f(h);rep(i, siz(e[x])) {if (e[x][i].fs == p) continue;dfs2(e[x][i].fs, x, e[x][i].sc, r + c.b(0, i) + c.b(i + 1, siz(e[x])) + cst * (n - cnt[x]), dfs2);//x==0}};dfs2(0, -1, 0, 0, dfs2);cout << ans << endl;}