Virus Tree 2 [AtCoder Beginner Contest 133 E]

https://atcoder.jp/contests/abc133/tasks/abc133_e

解説

https://atcoder.jp/contests/abc133/submissions/6312375

木でmod10^9+7なので、とりあえず木DPを疑う。
dp[cu] := cuを根とする部分木での塗り方の総数
これをベースにまずは考えてみよう。
正直これ以上は状態を増やせそうにない。
更新もよくするのだめっぽい。
こっちじゃないか。
　
木を使った問題はdfsを使うパターンがほとんどなので、次はそれで考える。
塗れる組み合わせは親につながっている頂点分は塗ることができなさそう。
これは使える性質だ。
木DPは子供側の抽象化して扱うものであるが、逆に親側が抽象化する方針もある。
dfs(cu, rest) := cuを根とする部分木で根を塗る方法がrest通りある時の塗り方。

int N, K;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
mint dfs(int cu, int pa, int rest) {
	mint res = rest;
	
	int used = 1; // 自分の色
	if (0 < cu) used++; // 親の色
	fore(to, E[cu]) if(to != pa) {
		res *= dfs(to, cu, K - used);
		used++;
	}

	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		E[a].push_back(b);
		E[b].push_back(a);
	}

	cout << dfs(0, -1, K) << endl;
}