首页 > 代码库 > Codechef Black Nodes in Subgraphs（树型背包）

Codechef Black Nodes in Subgraphs（树型背包）

2024-10-16 10:22:02   214人阅读

题目链接 Black Nodes in Subgraphs

题目意思就是在一棵树中所有点标记为两种颜色（黑和白）

然后询问是否存在大小为X恰好有Y个黑点的连通块

 

这题我们可以用树型背包的方法

设$f[i][j][0]$为以$i$为根的子树中大小为$j$的连通块的黑点数目的最小值，该连通块必须经过$i$

$f[i][j][1]$为以$i$为根的子树中大小为$j$的连通块的黑点数目的最大值，该连通块必须经过$i$

 

那么转移的时候有

$f[x][i + j][0] = min(f[x][i + j][0], f[x][i][0] + f[u][j][0]);$
$f[x][i + j][1] = max(f[x][i + j][1], f[x][i][1] + f[u][j][1]);$

 

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define rep(i, a, b)    for (int i(a); i <= (b); ++i)
 6 #define dec(i, a, b)    for (int i(a); i >= (b); --i)
 7 
 8 const int N = 5010;
 9 int f[N][N][2], sz[N];
10 vector <int> v[N];
11 int T, n, q;
12 int c[N], F[N], G[N];
13 
14 void dfs(int x, int fa){
15     sz[x] = 1;
16     if (c[x]) f[x][1][0] = f[x][1][1] = 1;
17     else      f[x][1][0] = f[x][1][1] = 0;
18 
19     for (auto u : v[x]){
20         if (u == fa) continue;
21         dfs(u, x);
22         dec(i, sz[x], 1){
23             rep(j, 1, sz[u]){
24                 f[x][i + j][0] = min(f[x][i + j][0], f[x][i][0] + f[u][j][0]);
25                 f[x][i + j][1] = max(f[x][i + j][1], f[x][i][1] + f[u][j][1]);
26             }
27         }
28 
29         sz[x] += sz[u];
30     }
31 
32     rep(i, 1, sz[x]){
33         F[i] = min(F[i], f[x][i][0]);
34         G[i] = max(G[i], f[x][i][1]);
35     }
36 }
37 
38 int main(){
39 
40     scanf("%d", &T);
41     while (T--){
42         scanf("%d%d", &n, &q);
43         rep(i, 0, n) v[i].clear();
44         memset(sz, 0, sizeof sz);
45         rep(i, 0, n) rep(j, 0, n) f[i][j][0] = 1 << 27, f[i][j][1] = 0;
46         rep(i, 0, n) F[i] = 1 << 27, G[i] = 0;
47         
48         rep(i, 1, n - 1){
49             int x, y;
50             scanf("%d%d", &x, &y);
51             v[x].push_back(y);
52             v[y].push_back(x);
53         }
54 
55         rep(i, 1, n) scanf("%d", c + i);
56         dfs(1, 0);
57 
58         for (; q--; ){
59             int x, y;
60             scanf("%d%d", &x, &y);
61             puts(F[x] <= y && G[x] >= y ? "Yes" : "No");
62         }
63     }
64 
65     return 0;
66 
67 }

 

Codechef Black Nodes in Subgraphs（树型背包）


联系
我们