Codeforces #808 : Div1 D. Partial Virtual Trees

問題文をもっと短く言おうとするとどうなるかな。
https://codeforces.com/contest/1707/problem/D

問題

1番の頂点を根とする、木を成す無向グラフが与えられる。
頂点集合SのPartial Virtual Treeとは、Sの真の部分集合S'のうち、S'内の2頂点のLCAもS'に含まれるようなものをいう。

元のグラフに対し、Partial Virtual Treeを取る作業をK回行った結果、根頂点だけになるような作業手順は何通りか。
K=1～(N-1)それぞれについて求めよ。

解法

「真の部分集合」の条件を除き、k回の作業で根頂点だけになる手順をf(k)とする。
真の解をg(k)とすると、

となる。あとはf(k)を求めよう。

f(k)は各頂点について、各子頂点を取り除くか取り除かないかのケースを葉から順に計算していくとよい。

int N;
int mo;
vector<int> E[2020];
ll dp[2020][2020];
ll S[2020][2020];
ll D[2020][2020];

ll comb(int P_,int Q_) {
	static const int N_=2020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}


void dfs(int cur,int pre) {
	int i,j;
	vector<vector<ll>> L,R;
	FOR(i,E[cur].size()) if(E[cur][i]==pre) {
		E[cur].erase(E[cur].begin()+i);
		break;
	}
	int C=E[cur].size();
	FORR(e,E[cur]) dfs(e,cur);
	
	L.resize(C+2),R.resize(C+2);
	L[0].resize(N+1,1);
	R[C+1].resize(N+1,1);
	FOR(i,C) {
		FOR(j,N+1) L[i+1].push_back(L[i][j]*S[E[cur][i]][j]%mo);
	}
	for(i=C-1;i>=0;i--) {
		FOR(j,N+1) R[i+1].push_back(R[i+2][j]*S[E[cur][i]][j]%mo);
	}
		
	if(cur) {
		FOR(i,C) {
			ll a=0;
			for(j=1;j<=N;j++) {
				(dp[cur][j]+=a*dp[E[cur][i]][j])%=mo;
				(a+=L[i][j]*R[i+2][j])%=mo;
			}
		}
	}
	for(i=1;i<=N;i++) {
		D[cur][i]=L[C][i];
		(dp[cur][i]+=D[cur][i])%=mo;
		S[cur][i]=(dp[cur][i]+S[cur][i-1])%mo;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,0);
	
	ll ret[2020]={};
	for(i=1;i<=N-1;i++) {
		ret[i]=dp[0][i];
		FOR(j,i) ret[i]+=mo-comb(i,j)*ret[j]%mo;
		ret[i]%=mo;
		cout<<ret[i]<<" ";
	}
	cout<<endl;
	
}

まとめ

意外にコード量増えるな。