CF735E Ostap and Tree

看到这题，有一个naive的DP做法, \(f[u][i][j]\) 表示 \(u\) 节点的子树内近的黑点距离为 \(i\)， 距离最远的非合法点距离为 \(j\)， 然后转移一下，貌似是能过的。
但我们可以再做一步小优化。
有一个很神奇的性质，就是当我们合并两棵非合法子树的时候，最深的非合法点并不会被消去，这个性质很好证明。
这告诉我们， 在非合法子树的转移中， \(j\) 的转移和 \(i\) 毫无关联。 那么，就可以把 \(i\), \(j\) 两维状态合并
\(f[u][x]\) 表示当 \(x \leq k\) 时则是本棵子树合法，并且子树内最近的染色点距离 \(u\) 为 \(x\)， \(k < x \leq 2k\) 时，表示最近的非合法点的距离距 \(u\) 的距离为 \(x - k - 1\)。
复杂度仅有 \(O(nk^2)\) 非常优秀，轻松通过本题。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 1e2 + 10, K = 45, mod = 1e9 + 7;

int n, k;
LL f[N][K], t[K];
vector<int> e[N];

inline void dfs(int u, int fa) {
	f[u][0] = 1, f[u][k + 1] = 1;
	for (auto v: e[u]) if (v ^ fa) {
		dfs(v, u);
		memset(t, 0, sizeof t);
		U(i, 0, 2 * k)
			U(j, 0, 2 * k) 
				(t[i + j <= 2 * k ? min(i, j + 1) : max(i, j + 1)]
				+= f[u][i] * f[v][j]) %= mod;
			memcpy(f[u], t, sizeof t);
	}
}

int main(){
	//FO("");
	read(n, k);
	U(i, 2, n) {
		int u, v;
		read(u, v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 1);
	LL ans = 0;
	U(i, 0, k) (ans += f[1][i]) %= mod;
	writeln(ans);
	return 0;
}