树形背包 $ O(N \sqrt N ) $
cpp
/*
题意：
求将树分解成k和k+1块的方案数
*/
#include <ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
int operator()(int x) const { return x ^ RANDOM; }
};
typedef gp_hash_table<int, int,chash> hash_t;
void solve(){
int n,m;
cin>>n>>m;
vector<int> adj[n+1],siz(n+1);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
if(m<=2*sqrt(n)){
vector<vector<int>> f(n+1,vector<int>(m+2));
vector<int> g(m+2);
function<void(int,int)> dfs1=[&](int u,int fa){
f[u][1]=1;
siz[u]=1;
for(auto v:adj[u]){
if(v==fa)continue;
dfs1(v,u);
for(int i=0;i<=m+1;i++)g[i]=0;
for(int j=min(m+1,siz[u]);j>=0;j--){
for(int k=min(m+1-j,siz[v]);k>=0;k--){
(g[j+k]+=f[u][j]*f[v][k]%mod)%=mod;
}
}
for(int i=0;i<=m+1;i++)f[u][i]=g[i];
siz[u]+=siz[v];
}
(f[u][0]+=f[u][m]+f[u][m+1])%=mod;
};
dfs1(1,0);
cout<<f[1][0]<<"\n";
return;
}
hash_t f[n+1];
function<void(int,int)> dfs2=[&](int u,int fa){
f[u][1]=1;
hash_t g;
for(auto v:adj[u]){
if(v==fa)continue;
dfs2(v,u);
for(auto &[j,val1]:f[u]){
for(auto &[k,val2]:f[v]){
if(j+k>m+1)continue;
(g[j+k]+=val1*val2%mod)%=mod;
}
}
f[u].clear();
for(auto [i,val]:g)f[u][i]=val;
g.clear();
}
(f[u][0]+=f[u][m]+f[u][m+1])%=mod;
vector<int> tmp;
for(auto &[i,val]:f[u]){
if(!val)tmp.push_back(i);
}
for(auto &it:tmp)f[u].erase(it);
};
dfs2(1,0);
cout<<f[1][0]<<"\n";
}