一道思路不难但是写起来很麻烦的树形背包
我们发现每个节点有很多信息需要保留
所以就暴力的设\(f[u][j][0/1][0/1]\)表示点u的子树分配了j个监察器,点u有没有被控制,点u放没放监察器
然后就分四种情况暴力讨论就好了
注意背包的时候要卡常数
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>const int M = 100005 ;const int N = 103 ;const int mod = 1e9 + 7 ;using namespace std ;inline int read() { char c = getchar() ; int x = 0 , w = 1 ; while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; } while(c>='0' && c<='9') { x=x*10+c-'0' ; c = getchar() ; } return x*w ; }int n , m , num , hea[M] ;int f[M][N][2][2] , g[N][2][2] , size[M] ;struct E { int nxt , to ; } edge[M * 2] ;inline void add_edge(int from , int to) { edge[++num].nxt = hea[from] ; edge[num].to = to ; hea[from] = num ;}void dfs(int u , int father) { size[u] = 1 ; f[u][0][0][0] = f[u][1][0][1] = 1 ; for(int i = hea[u] ; i ; i = edge[i].nxt) { int v = edge[i].to ; if(v == father) continue ; dfs(v , u) ; for(int j = 0 ; j <= min(m , size[u]) ; j ++) { g[j][0][0] = f[u][j][0][0] ; f[u][j][0][0] = 0 ; g[j][0][1] = f[u][j][0][1] ; f[u][j][0][1] = 0 ; g[j][1][0] = f[u][j][1][0] ; f[u][j][1][0] = 0 ; g[j][1][1] = f[u][j][1][1] ; f[u][j][1][1] = 0 ; } for(int j = 0 ; j <= min(size[u] , m) ; j ++) { for(int k = 0 ; k <= size[v] && j + k <= m ; k ++) { f[u][j + k][0][0] = (f[u][j + k][0][0] + 1LL * g[j][0][0] * f[v][k][1][0]) % mod ; f[u][j + k][0][1] = (f[u][j + k][0][1] + 1LL * g[j][0][1] * (f[v][k][1][0] + f[v][k][0][0]) % mod) % mod ; f[u][j + k][1][0] = ((f[u][j + k][1][0] + 1LL * g[j][1][0] * (f[v][k][1][0] + f[v][k][1][1]) % mod) % mod + 1LL * g[j][0][0] * f[v][k][1][1] % mod) % mod ; f[u][j + k][1][1] = ((f[u][j + k][1][1] + 1LL * g[j][1][1] * (((f[v][k][1][0] + f[v][k][1][1]) % mod + f[v][k][0][0] ) % mod + f[v][k][0][1]) % mod ) % mod + 1LL * g[j][0][1] * (f[v][k][0][1] + f[v][k][1][1]) % mod) % mod ; } } size[u] += size[v] ; }}int main() { n = read() ; m = read() ; for(int i = 1 , u , v ; i < n ; i ++) { u = read() ; v = read() ; add_edge(u , v) ; add_edge(v , u) ; } dfs(1 , 1) ; printf("%d\n",(f[1][m][1][0] + f[1][m][1][1]) % mod) ; return 0 ;}
