ACM模版
描述
题解
这个题做出来的人很少，看了看官方题解，如下：
我们令
dp[i][j]
表示以 i 为根且当前联通块大小为 k 的方案总数，特别的，
dp[i][0]
表示割点当前点与其父亲是棵平衡树的方案总数。 对于 u 的一个孩子 v 可以得到转移方程
dp[u][j+k]=dp[u][j]∗dp[v][k]
另外
dp[u][0]=Σdp[u][j](j>=题目给定的k)
这样乍看是
n3
的，有一个技巧可以做到
n2
即每次 dp 时，只枚举当前 u 所在子树的大小，每当枚举到它的其中孩子时，当前 u 所在子树的大小加上它孩子为根的子树的大小。可以理解为每一个点对只被枚举到一次。 最后答案即为
dp[root][0]
。
这个题虽然有官方题解，但是看着我也是一脸懵逼，只是清楚的知道这是一个树归，思前想后，于是找到了一个 AC 代码研究了一番，大致算是明白了，但是状态转移方程依然是似懂非懂……如果哪个大牛有高见，烦指教~~~
暂且说一下我的理解，因为这里是平衡树，所以没有确定几个分叉，只是确定高度差不大于一，所以我的理解是，一棵以 u 为根的树，无论去哪一棵子树，并且这个子树的根是 u 的孩子，那么最后一定都满足平衡，本着这样的思路，利用乘法原理可以得到如上转移方程。
不知我的理解是否有偏差，如果有的话，烦请告知！
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN =
2222;
const int MOD =
1e9 +
7;
int n, k;
int tot =
0;
int pre[MAXN];
int dp[MAXN][MAXN];
int s[MAXN];
struct edge
{
int next;
int to;
} e[MAXN <<
1];
void AND_MOD(
int &x,
int y)
{
x += y;
if (x >= MOD)
{
x -= MOD;
}
}
void dfs(
int u,
int fa)
{
dp[u][s[u] =
1] =
1;
for (
int it = pre[u]; it; it = e[it].next)
{
if (e[it].to == fa)
{
continue;
}
dfs(e[it].to, u);
for (
int i = s[u]; i >
0; i--)
{
for (
int j = s[e[it].to]; j >
0; j--)
{
AND_MOD(dp[u][i + j], (
long long)dp[u][i] * dp[e[it].to][j] % MOD);
}
dp[u][i] = (
long long)dp[u][i] * dp[e[it].to][
0] % MOD;
}
s[u] += s[e[it].to];
}
for (
int i = k; i <= s[u]; i++)
{
AND_MOD(dp[u][
0], dp[u][i]);
}
}
int main()
{
cin >> n >> k;
int u, v;
for (
int i =
1; i < n; ++i)
{
scanf(
"%d%d", &u, &v);
e[++tot] = (edge){pre[u], v};
pre[u] = tot;
e[++tot] = (edge){pre[v], u};
pre[v] = tot;
}
dfs(
1, -
1);
printf(
"%d\n", dp[
1][
0]);
return 0;
}
