Master of Subgraph

发表于 | 阅读数

给你一棵树 询问现在小于等于$m$的权值出现情况 权值是任意联通子树的点权和。

$n\leq 3\times 10^3,m\leq 10^5$

考虑暴力解决，$dp[x]$表示$x$往下可以组成多少种，显然$dp[x][j+a[x]]=dp[u][j]$

只需要是否存在，显然可以$bitset$优化,需要注意的是。

  • 一开始想处理每个子树可形成的再合并，考虑背包合并不太可能。
  • 合并其他子树的时候带着其他子树的消息即可。
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

#include <bits/stdc++.h>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 3e3 + 10;
const int mod = 1e9 + 7;
const int M = 1e6 + 10;

int siz[N], f[N], vis[N];
int rt, gcnt;
vector<int> g[N];
void GetRoot(int x, int fa)
{
    siz[x] = 1;
    f[x] = 0;
    for (int to : g[x])
    {
        if (to == fa || vis[to])
            continue;
        GetRoot(to, x);
        siz[x] += siz[to];
        f[x] = max(f[x], siz[to]);
    }
    f[x] = max(f[x], gcnt - siz[x]);
    if (f[x] < f[rt])
        rt = x;
}
bitset<100005> b[N], ans;
int a[N];
void work(int x, int fa)
{
    b[x] <<= a[x];
    for (int to : g[x])
    {
        if (vis[to] || to == fa)
            continue;
        b[to] = b[x];
        work(to, x);
        b[x] |= b[to];
    }
}
void calc(int x)
{

    b[x].reset();
    b[x][a[x]] = 1;
    for (int to : g[x])
    {
        if (vis[to])
            continue;
        b[to] = b[x];
        work(to, x);
        b[x] |= b[to];
    }
    ans |= b[x];
}
void solve(int x)
{

    vis[x] = 1;
    calc(x);
    for (int to : g[x])
    {
        if (vis[to])
            continue;
        gcnt = siz[to];
        rt = 0;

        GetRoot(to, x);

        solve(rt);
    }
}
int n, T, m;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        ans.reset();
        for (int i = 1; i <= n; i++)
            g[i].clear(), vis[i] = 0;
        for (int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);

            g[u].push_back(v);
            g[v].push_back(u);
        }
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        f[0] = 1e9;
        rt = 0;
        gcnt = n;
        GetRoot(1, 0);

        solve(rt);
        for (int i = 1; i <= m; i++)
            printf("%d", (int)ans[i]);
        printf("\n");
    }
}