Typical DP Contest P - うなぎ

問題

N頂点からなる木に、交わらないK本のパスを書く書きかたは何通りあるか。mod 10^9 + 7で求めよ。
パスを書く順序は区別しない。

制約条件

N≦1000
K≦50

解法

dp[i][j][k] :=
頂点iを根とする部分木で、j本のパスを描き、頂点iから出るパスの本数をk本とするときの場合の数
を更新するようなDPをすればよい。

更新するのにはもう一回小さいDPをすればよくて、
dp2[子の何番目まで見たか][今までの子まででのパスの本数][親にいるパスの本数] := 場合の数
として、子ごとに更新していけばよい。

更新は、親にパスをつなぐかどうか2通りの遷移がある。

ソースコード

const int mod = inf + 7;
int n, path;
int dp[1000][52][3];
vector<vi> e;

void rec(int c, int p){
	
	vector<vector<vi> > dp2(2, vector<vi>(52, vi(3)));
	int cur = 0, next = 1;
	
	dp2[0][0][0] = 1;
	
	rep(i, e[c].size()) if(e[c][i] != p){
		
		rec(e[c][i], c);
		for(int j = path; j >= 0; j--) rep(k, 3){
			
			rep(l, path - j + 2) rep(m, 3){
				
				int way = (ll)dp2[cur][j][k] * dp[e[c][i]][l][m] % mod;
				//つなげる
				if(m < 2 && k < 2){
					int nj = j + l;
					if(k == 0 && m == 0) nj++;
					if(k == 1 && m == 1) nj--;
					if(0 <= nj && nj <= path) (dp2[next][nj][k + 1] += way) %= mod;
				}
				//つなげない
				if(j + l <= path) (dp2[next][j + l][k] += way) %= mod;
			}
		}
		swap(cur, next);
		dp2[next] = vector<vi>(52, vi(3));
	}
	rep(i, path + 1) rep(j, 3) dp[c][i][j] = dp2[cur][i][j];
}

int main(){
	cin >> n >> path;
	e.resize(n);
	rep(i, n - 1){
		int a, b;
		cin >> a >> b; a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	rec(0, 0);
	int ans = 0;
	rep(i, 3) (ans += dp[0][path][i]) %= mod;
	cout << ans << endl;
	
	return 0;
}