結果
問題 | No.1124 Earthquake Safety |
ユーザー |
![]() |
提出日時 | 2020-07-22 22:38:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 543 ms / 3,000 ms |
コード長 | 1,798 bytes |
コンパイル時間 | 1,269 ms |
コンパイル使用メモリ | 126,832 KB |
最終ジャッジ日時 | 2025-01-12 03:15:01 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 58 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; const ll MOD=1e9+7; const ll inv2=5e8+4; vector<int> g[300030]; ll ans; ll dp[300030]; void dfs(int x, int p){ ll s=0; for(auto y:g[x]){ if(y==p) continue; dfs(y, x); ll z=inv2*dp[y]%MOD; (dp[x]+=z)%=MOD; (s+=z*z)%=MOD; } (ans+=dp[x]*6)%=MOD; (ans+=(dp[x]*dp[x]-s+MOD)*3)%=MOD; dp[x]=(dp[x]+1)%MOD; } ll dp2[300030]; const ll inv6=(MOD+1)/6; const ll inv8=(MOD+1)/8; void dfs2(int x, int p){ ll s=0; for(auto y:g[x]){ if(y==p) continue; (s+=dp[y])%=MOD; } for(auto y:g[x]){ if(y==p) continue; dp2[y]=(1+inv2*(s-dp[y]+dp2[x]))%MOD; } ll s1=0, s2=0, s3=0; for(auto y:g[x]){ if(y==p){ (s1+=dp2[x])%=MOD; (s2+=dp2[x]*dp2[x])%=MOD; (s3+=dp2[x]*dp2[x]%MOD*dp2[x])%=MOD; }else{ (s1+=dp[y])%=MOD; (s2+=dp[y]*dp[y])%=MOD; (s3+=dp[y]*dp[y]%MOD*dp[y])%=MOD; } } (ans+=(s1*s1-s2+MOD)%MOD*inv8%MOD*6)%=MOD; (ans+=(s1*s1%MOD*s1+2*s3-3*s2*s1%MOD+MOD)%MOD*inv8%MOD)%=MOD; for(auto y:g[x]){ if(y==p) continue; dfs2(y, x); } } int main() { int n; cin>>n; if(n==1){ cout<<1<<endl; return 0; } for(int i=0; i<n-1; i++){ int a, b; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } ans=n; dfs(0, -1); dfs2(0, -1); for(int i=0; i<n-1; i++) ans=ans*2%MOD; cout<<ans<<endl; return 0; }