BZOJ5314 潜入行动
看到这道题就很容易想到一个裸的$O(nk^2)$的 DP，但是时间复杂度上似乎不是很能承受，但是实际上这个题的时间复杂度是 $O(nk)$的。分三类情况讨论，一种是两个子树大小都大于 $k$的，这个时候合并复杂度为$k^2$，但是这样的情况最多出现 $\frac{n}{k}$次。第二种是一个大于 $k$，一个小于等于 $k$，这个时候对于小于等于 $k$ 的节点的子树，每个点贡献一个 $k$ 的复杂度，同时可以发现每个点最多贡献一次，因为小于 $k$ 的向上合并一次就必定大于等于 $k$ 了。最后是两个点都小于等于 $k$ 的，复杂度可以均摊到每个节点上，这样复杂度也是 $O(nk)$ 的。
具体实现的时候可能需要一些寻址的常数优化。
时间复杂度 $O(nk)$。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add(a, b)
#define cpop(a,b) a = pop(a, b)
#define cmul(a,b) a = mul(a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define bin(i) (1 << (i))
#define SZ(x) (int)x.size()
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & a, T b) { return b > a ? a = b, true : false; }
template<typename T> inline bool cmin(T & a, T b) { return b < a ? a = b, true : false; }
const int MAXN = 1e5 + 5;
const int MAXK = 105;
const int oo = 0x3f3f3f3f;
const int mod = 1e9 + 7;
inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return (ll)a * b % mod;}
int N, K;
struct edge {
int y, next;
}e[MAXN << 1];
int LINK[MAXN], len = 0, f[MAXN][MAXK][2][2], siz[MAXN], g[MAXK][2][2];
inline void ins(int x, int y){
e[++len].next = LINK[x]; LINK[x] = len;
e[len].y = y;
}
inline void Ins(int x, int y){
ins(x, y);
ins(y, x);
}
void DFS(int node, int fa){
f[node][0][0][0] = f[node][1][0][1] = 1; siz[node] = 1;
Auto (i, node) if (e[i].y != fa) {
DFS(e[i].y, node);
siz[node] += siz[e[i].y];
}
if (!fa) return;
int n = min(K, siz[node]);
up (i, 0, n) {
int m = min(K - i, siz[fa]);
up (j, 0, m) {
int *ss[2], *tt[2];
up (k, 0, 1) {
ss[k] = f[node][i][k];
tt[k] = f[fa][j][k];
}
if (ss[0][0]) {
cadd(g[i + j][0][1], mul(ss[0][0], tt[0][1]));
cadd(g[i + j][1][1], mul(ss[0][0], tt[1][1]));
}
if (ss[0][1]) {
cadd(g[i + j][1][1], mul(ss[0][1], tt[0][1]));
cadd(g[i + j][1][1], mul(ss[0][1], tt[1][1]));
}
if (ss[1][0]) {
cadd(g[i + j][0][0], mul(ss[1][0], tt[0][0]));
cadd(g[i + j][0][1], mul(ss[1][0], tt[0][1]));
cadd(g[i + j][1][0], mul(ss[1][0], tt[1][0]));
cadd(g[i + j][1][1], mul(ss[1][0], tt[1][1]));
}
if (ss[1][1]) {
cadd(g[i + j][1][0], mul(ss[1][1], tt[0][0]));
cadd(g[i + j][1][0], mul(ss[1][1], tt[1][0]));
cadd(g[i + j][1][1], mul(ss[1][1], tt[0][1]));
cadd(g[i + j][1][1], mul(ss[1][1], tt[1][1]));
}
}
}
n = min(K, siz[fa] + siz[node]);
up (i, 0, n) {
memcpy(f[fa][i], g[i], sizeof(g[i]));
memset(g[i], 0, sizeof(g[i]));
}
}
int main(){
scanf("%d%d", &N, &K);
up (i, 2, N) {
int x, y; scanf("%d%d", &x, &y);
Ins(x, y);
}
DFS(1, 0);
printf("%d\n", add(f[1][K][1][0], f[1][K][1][1]));
return 0;
}
