题解
一道思路不难但是写起来很麻烦的树形背包
我们发现每个节点有很多信息需要保留
所以就暴力的设\(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 ;}[JSOI2018]潜入行动
原文地址：https://www.cnblogs.com/beretty/p/10306252.html