python/TangDou/JiShuanKe/2023-03-06/T3702.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 2100, M = N << 1;
const int MOD = 998244353;

int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int n;
int limit[N]; // 以u为根的子树中数量上限
int st[N];    // 是不是访问过

LL f[N][N];

void dfs(int u) {
    st[u] = 1;                 // 访问过了
    f[u][0] = 1;               // u子树中，放0个苹果的方案是1，此时只能是不管有多少个子结点，都是啥也不能放，方案唯一
    if (limit[u]) f[u][1] = 1; // 在u子树中，如果只放1个的话，那么必然是放在u节点上，否则u子树就不存在的，此时方案数是1

    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (st[v]) continue;
        dfs(v);

        // 分组背包
        for (int j = limit[u]; j >= 0; j--) // 枚举u子树体积,倒序降维
            // Q:为什么这里k=0开始是错的呢？
            for (int k = 1; k <= min(j, limit[v]); k++) // 枚举决策,v子树中放资源k个
                f[u][j] = (f[u][j] + f[v][k] * f[u][j - k]) % MOD;
    }
}
int main() {
    freopen("appletree.in", "r", stdin);
    freopen("appletree.out", "w", stdout);

    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> limit[i];

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a); // 无向图
    }

    dfs(1);

    int res = 0;
    for (int i = 0; i <= limit[1]; i++) res = (res + f[1][i]) % MOD;

    printf("%d\n", res);
    return 0;
}