[JSOI2018]潛入行動

題解

一道思路不難但是寫起來很麻煩的樹形背包

我們發現每個節點有很多信息需要保留

所以就暴力的設\(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 ;
}