kmjp's blog

競技プログラミング参加記です

AtCoder ABC #149 : F - Surrounded Nodes

これも典型かな…。
https://atcoder.jp/contests/abc149/tasks/abc149_f

問題

木を成す無向グラフが与えられる。
各頂点を、それぞれ1/2の確率で白か黒に塗る。
黒く塗った点を含む最小の部分グラフ中における白頂点数の期待値を求めよ。

解法

各頂点において、そこが白く塗られ、かつそこから伸びる各辺のうち2か所以上の延長で黒頂点が1個以上現れればよいので、その確率を求めよう。
まず対象の頂点が白く塗られる確率は1/2である。
各辺の先にある頂点数の配列をCとする。
頂点数cである辺の先に1個でも黒頂点がある確率は1-(1/2)^cである。
あとはそのような辺が2個以上であるケースをDPで求めよう。

int N;
vector<int> E[201010];
int C[201010];
const ll mo=1000000007;
ll ret;

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;
}

int dfs(int cur,int pre) {
	C[cur]=1;
	vector<ll> B;
	FORR(e,E[cur]) if(e!=pre) {
		
		B.push_back(dfs(e,cur));
		C[cur]+=B.back();
	}
	if(C[cur]<N) B.push_back(N-C[cur]);
	
	ll P[3]={(mo+1)/2,0,0};
	FORR(b,B) {
		ll w=modpow((mo+1)/2,b);
		b=(1+mo-w)%mo;
		ll Q[3]={};
		Q[0]=P[0]*w%mo;
		Q[1]=(P[1]*w+P[0]*b)%mo;
		Q[2]=(P[2]+P[1]*b)%mo;
		swap(P,Q);
	}
	
	ret+=P[2];
	
	return C[cur];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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,-1);
	cout<<ret%mo<<endl;
}

まとめ

本番なんかトラブルでもあった?