yukicoder : No.196 典型DP (1)

確かに典型ではある。
http://yukicoder.me/problems/234

問題

N頂点の根付き木が与えられる。

このうち一部の頂点を黒く塗りたい。
ただし、黒く塗った頂点のsubtree内の頂点は、全て黒く塗られていなければならない。

黒頂点がK個であるような塗り分け方が何通りあるか求めよ。

解法

各頂点xについて、subtree内でy個黒頂点がある塗り分け方をDP(x,y)とする。
子頂点から順にDP(x,y)を求め、各頂点でDPして子頂点のDP(x,y)からDP(x,y)を計算していく。

x自体を塗るときはsubtreeを全部塗らないと行けないので、subtree内の頂点数をs(x)とするとDP(x,s(x))=1になる点に注意。

int N,K;
vector<int> E[2050];
ll val[2050][2050];
ll mo=1000000007;
int num[2050];

void dfs(int cur,int pre) {
	int i,j,x;
	vector<ll> nn[2];
	nn[0]=vector<ll>(2020,0);
	nn[1]=vector<ll>(2020,0);
	
	FOR(i,E[cur].size()) if(E[cur][i]==pre) break;
	if(i<E[cur].size()) E[cur].erase(E[cur].begin()+i);
	
	num[cur]=1;
	nn[0][0]=1;
	
	FOR(x,E[cur].size()) {
		int cu=x%2,ta=cu^1;
		int tar=E[cur][x];
		FOR(i,2020) nn[ta][i]=0;
		
		dfs(tar,cur);
		for(i=0;i<=num[tar];i++) if(val[tar][i]) {
			for(j=0;j<num[cur];j++) nn[ta][i+j] += nn[cu][j]*val[tar][i]%mo;
		}
		num[cur]+=num[tar];
		FOR(i,num[cur]+1) nn[ta][i] %= mo;
	}
	
	FOR(i,2010) val[cur][i]=nn[E[cur].size()%2][i];
	val[cur][num[cur]]=1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(0,-1);
	cout<<val[0][K]<<endl;
}

まとめ

典型と言えば典型なので、★３か４か迷うところですね。