Codeforces #718 Div1+2 : F. Reunion

どっかでに出てきてそうな問題ではある。
https://codeforces.com/contest/1517/problem/F

問題

N頂点の木を成すグラフが与えられる。
各点をそれぞれ1/2の確率で白黒に塗り分ける。
黒頂点をすべて含む最小の部分グラフの直径の総和を求めよ。

解法

全塗り分けパターンで仮に直径がNとすると、問題の総和はN*(2^N)である。
そこから、「直径がR以下である塗り分けがf(R)通りなら、f(R)を引く」ということをR=0～Nに対して行う。
これはよくある木DPで、SubTree内の最も深い点までの距離に対する組み合わせを保持していけばよい。

int N;
vector<int> E[101010];
const ll mo=998244353;
ll F[303][303];
ll G[303][303];
int D[303];
int K;

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) {
	
	D[cur]=0;
	ZERO(F[cur]);
	ZERO(G[cur]);
	F[cur][0]=G[cur][0]=1;
	
	int i,j;
	FORR(e,E[cur]) if(e!=pre) {
		dfs(e,cur);
		ll TF[303]={};
		ll TG[303]={};
		FOR(i,D[cur]+1) FOR(j,D[e]+1) {
			int mi=min(i,j+1);
			int ma=max(i,j+1);
			(TF[ma]+=F[cur][i]*F[e][j])%=mo;
			(TG[mi]+=G[cur][i]*G[e][j])%=mo;
			if(i+j+1<=K) {
				(TG[i]+=G[cur][i]*F[e][j])%=mo;
				(TG[j+1]+=F[cur][i]*G[e][j])%=mo;
			}
			else {
				(TF[i]+=F[cur][i]*G[e][j])%=mo;
				(TF[j+1]+=G[cur][i]*F[e][j])%=mo;
			}
		}
		
		FOR(i,K+1) {
			F[cur][i]=TF[i];
			G[cur][i]=TG[i];
		}
		
		D[cur]=max(D[cur],D[e]+1);
	}
	
	
	return D[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);
	}
	
	ll ret=N*modpow(2,N)%mo;
	for(i=0;i<=N;i++) {
		K=i;
		dfs(0,0);
		FOR(j,K+1) (ret-=G[0][j])%=mo;
	}
	
	cout<<(ret%mo+mo)*modpow(modpow(2,N))%mo<<endl;
	
}

まとめ

なかなか追い付かない…。