こっちの方が簡単だった。
https://yukicoder.me/problems/no/1124
問題
木を成す無向グラフが与えられる。
ここからいくつかの辺を切断した後、各頂点iの属する連結成分のサイズをD[i]としたとき、グラフのスコアをD[i]の2乗和とする。
辺の切断の仕方(2^(辺の数))通りにおけるスコアの総和を求めよ。
解法
Editorialは「頂点の属するサイズの2乗和→連結成分のサイズの3乗和」として解いているけど、あちらの方が難しい気がする。
各辺が1/2の確率で切断されると考え、連結成分のサイズとその2乗の期待値を全方位木DPしていくことでも解ける。
int N; vector<int> E[302020]; const ll mo=1000000007; ll A[303030],B[303030]; ll p2[303030],r2; ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void dfs(int cur,int pre) { A[cur]=B[cur]=1; FORR(e,E[cur]) if(e!=pre) { dfs(e,cur); ll a=(A[cur]+A[cur]+A[e])*r2%mo; ll b=(B[cur]+B[cur]+B[e]+2*(A[cur]*A[e]))%mo*r2%mo; A[cur]=a; B[cur]=b; } } void dfs2(int cur,int pre, ll PA, ll PB) { ll a=(A[cur]+A[cur]+PA)*r2%mo; ll b=(B[cur]+B[cur]+PB+2*(A[cur]*PA))%mo*r2%mo; A[cur]=a; B[cur]=b; FORR(e,E[cur]) if(e!=pre) { ll XA=((A[cur]-A[e]*r2%mo)+mo)%mo; ll XB=((B[cur]-XA*A[e]%mo-B[e]*r2%mo)%mo+mo)%mo; dfs2(e,cur,XA,XB); } } void solve() { int i,j,k,l,r,x,y; string s; r2=(mo+1)/2; p2[0]=1; FOR(i,300101) p2[i+1]=p2[i]*2%mo; cin>>N; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(0,0); dfs2(0,0,0,0); ll ret=0; FOR(i,N) ret+=B[i]*p2[N-1]%mo; cout<<ret%mo<<endl; }
まとめ
いやとっさに思い浮かんだのこっちだし、本番Editorialの方法で解いた人多いのかな?