結果
問題 | No.1333 Squared Sum |
ユーザー |
|
提出日時 | 2021-01-09 12:30:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 185 ms / 2,000 ms |
コード長 | 3,610 bytes |
コンパイル時間 | 1,958 ms |
コンパイル使用メモリ | 197,168 KB |
最終ジャッジ日時 | 2025-01-17 15:34:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#line 2 "/home/defineprogram/Desktop/Library/template/template.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define rep(i, n) for (int i = 0; i < n; i++) #define REP(i, n) for (int i = 1; i < n; i++) #define rev(i, n) for (int i = n - 1; i >= 0; i--) #define all(v) v.begin(), v.end() #define P pair<ll, ll> #define len(s) (ll) s.size() template <class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true; } return false; } template <class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true; } return false; } constexpr ll inf = 3e18; #line 3 "/home/defineprogram/Desktop/Library/math/extgcd.cpp" ll extGCD(ll a, ll b, ll &x, ll &y) { if (!b) { x = 1; y = 0; return a; } ll d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } ll modinv(ll a, ll m) { ll x, y; extGCD(a, m, x, y); return (x % m + m) % m; } #line 4 "/home/defineprogram/Desktop/Library/math/modint.cpp" template <int MOD> struct mint { int32_t n; mint() : n(0) {} mint(ll x) : n(x >= 0 ? x % MOD : (MOD - (-x) % MOD) % MOD) {} mint &operator+=(const mint &p) { if ((n += p.n) >= MOD) n -= MOD; return *this; } mint &operator-=(const mint &p) { if ((n += MOD - p.n) >= MOD) n -= MOD; return *this; } mint &operator*=(const mint &p) { n = 1ll * n * p.n % MOD; return *this; } mint &operator/=(const mint &p) { *this *= p.inverse(); return *this; } mint operator-() const { return mint(-n); } mint operator+(const mint &p) const { return mint(*this) += p; } mint operator-(const mint &p) const { return mint(*this) -= p; } mint operator*(const mint &p) const { return mint(*this) *= p; } mint operator/(const mint &p) const { return mint(*this) /= p; } bool operator==(const mint &p) const { return n == p.n; } bool operator!=(const mint &p) const { return n != p.n; } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.n; } friend istream &operator>>(istream &is, mint &p) { int x; is >> x; p = mint(x); return is; } mint pow(int64_t x) const { mint res(1), mul(n); while (x > 0) { if (x & 1) res *= mul; mul *= mul; x >>= 1; } return res; } mint inverse() const { return mint(modinv(n,MOD)); } }; /* @brief mod int @docs docs/modint.md */ #line 3 "main.cpp" constexpr int mod=1e9+7; using modint=mint<mod>; int N; vector<pair<int,modint>>G[1<<18]; modint dp1[1<<18],dp2[1<<18]; modint cld[1<<18]; modint ans=0; void dfs1(int x,int p){ cld[x]+=1; for(auto i:G[x])if(i.first!=p){ dfs1(i.first,x); dp1[x]+=dp1[i.first]+i.second*cld[i.first]; cld[x]+=cld[i.first]; ans+=i.second*i.second*cld[i.first]*(modint(N)-cld[i.first]); } } void dfs2(int x,int p){ for(auto i:G[x])if(i.first!=p){ modint par=dp2[x]-dp1[i.first]-i.second*cld[i.first]; ans+=(par*cld[i.first]+dp1[i.first]*(modint(N)-cld[i.first]))*i.second; dp2[i.first]=dp1[i.first]+par+i.second*(modint(N)-cld[i.first]); dfs2(i.first,x); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin>>N; rep(i,N-1){ int a,b,c;cin>>a>>b>>c;a--;b--; G[a].push_back({b,c}); G[b].push_back({a,c}); } dfs1(0,0); dp2[0]=dp1[0]; dfs2(0,0); cout<<ans<<"\n"; }