TopCoder SRM 604 Div2 Hard FoxConnection2

Div1 Mediumと似たテーマだけど、こちらの方が簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=12951

問題

N点からなる木が与えられる。
このうちK点を選択し、それらの点が連結している(選択した点同士をたどる場合、非選択の点を通過しない)組み合わせ数を答えよ。

解法

重複を防ぐため、K個に含む最小の番号iを定め、i番の点をrootとして(i+1番以降の点だけを用いて)K個の点を選択する組み合わせを考えればよい。

各頂点jの先にあと何個の点を選択するかを状態として持つ。

• 選択する点が0個なら、j以降は何も選択しない、の１通り。
• 選択する点が1個なら、j番だけ選択する、の１通り。
• 選択する点が2個以上なら、まずはj番を選択し、残りの選択数を各子ノードに振り分け、組み合わせ数をDPする。

int K;
vector<int> E[52];
ll mo=1000000007;
ll pat[52][52];

class FoxConnection2 {
	public:
	
	ll dfspat(int cur,int pre,int mimi,int left) {
		if(left<=1) return 1;
		if(pat[cur][left]>=0) return pat[cur][left];
		left--;
		
		ll dp[2][51];
		ZERO(dp);
		dp[0][left]=1;
		int i,x,y;
		FOR(i,E[cur].size()) {
			int curr=i%2,tar=curr^1;
			int nep=E[cur][i];
			if(nep==pre || nep<mimi) {
				memmove(dp[tar],dp[curr],sizeof(dp[tar]));
			}
			else {
				ZERO(dp[tar]);
				FOR(x,left+1) FOR(y,x+1) {
					dp[tar][x-y] += dp[curr][x]*dfspat(nep,cur,mimi,y);
					dp[tar][x-y] %= mo;
				}
			}
		}
		return pat[cur][left+1]=dp[E[cur].size()%2][0];
	}
	
	int ways(vector <int> A, vector <int> B, int k) {
		int N=A.size()+1;
		K=k;
		int i,x,y;
		
		FOR(x,N) E[x].clear();
		FOR(x,N-1) E[A[x]-1].push_back(B[x]-1),E[B[x]-1].push_back(A[x]-1);
		
		ll ret=0;
		FOR(x,N) {
			MINUS(pat);
			ret += dfspat(x,51,x,k);
		}
		return (int)(ret%mo);
	
	}
};

まとめ

こういう木をたどる問題はCodeforcesでよくやったね。