[Codeforces] 855C. Helga Hufflepuff's Cup

題目連結:http://codeforces.com/contest/855/problem/C

---

賽中看到一堆大大們都寫出來的題目，但是自己怎麼寫都寫不出來就是了QQ，一定是因為我DP太爛的緣故
總之這題很明顯就是個樹DP題，狀態這裡是定成 $$dp[i][x][0] := 第i個節點放[1,k-1]種類且有x個k的方法數 \\ dp[i][x][1] := 第i個節點放k且有x個k的方法數 \\ dp[i][x][2] := 第i個節點放[k+1,M]且有x個k的方法數$$ 轉移的話就算滿好想的了，大致就是0號可以從0,1,2轉來；2只能從0轉來；ㄉ可以從0, 2轉來，而怎麼轉就直接枚舉其中一邊有幾個就好了。

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef long long lld;
const int N = 100000 + 5;
const int K = 10 + 2;
const int MOD_BASE = 1e9+7;
	
int n, m, k, x;
lld dp[N][K][3];
vector<int> G[N];
void dfs(int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<n-1;i++){
		int u, v; cin>>u>>v;
		G[u].PB(v);
		G[v].PB(u);
	}
	cin>>k>>x;
	dfs(1, 1);
	lld ans = 0;
	for(int i=0;i<=x;i++){
		ans=(ans+dp[1][i][0])%MOD_BASE;
		ans=(ans+dp[1][i][1])%MOD_BASE;
		ans=(ans+dp[1][i][2])%MOD_BASE;
	}
	cout<<ans<<'\n';
	return 0;
}

void dfs(int w, int f){
	dp[w][1][1]=1;
	dp[w][0][0]=k-1;
	dp[w][0][2]=m-k;
	for(auto i: G[w]){
		if(i==f) continue;
		dfs(i, w);
		lld ndp[K][3]={0};
		for(int kk=0;kk<=x;kk++){
			for(int j=0;j<=kk;j++){
				ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
				ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][1])%MOD_BASE)%MOD_BASE;
				ndp[kk][0] = (ndp[kk][0]+(dp[w][j][0]*dp[i][kk-j][2])%MOD_BASE)%MOD_BASE;

				ndp[kk][1] = (ndp[kk][1]+(dp[w][j][1]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;

				ndp[kk][2] = (ndp[kk][2]+(dp[w][j][2]*dp[i][kk-j][0])%MOD_BASE)%MOD_BASE;
				ndp[kk][2] = (ndp[kk][2]+(dp[w][j][2]*dp[i][kk-j][2])%MOD_BASE)%MOD_BASE;
			}
		}
		for(int ii=0;ii<=x;ii++){
			for(int j=0;j<3;j++){
				dp[w][ii][j]=ndp[ii][j];
			}
		}
	}
}

C++