题解：P12002 吃猫粮的玉桂狗

· · 题解

一道很好的 dp 题，感觉之前有见过这种套路，一下还是不会做。

题目中的限制 (x,y) 相当于是树中不存在父亲是 x 并且儿子是 y。观察到题目中有一个特别的条件是：保证 c_i \geq \lfloor\frac{n}{2}\rfloor。这有什么用处呢？这样就可以保证只有最多一种猫粮超出了 c_i 的限制。考虑容斥，合法的方案即是总的方案数减掉有一种猫粮超出数量限制的方案。总的方案是比较好计算的，f2[u][i] 表示 u 节点放的是 i 这种猫粮其子树内的方案数。有转移：

f2[u][i] = \prod_{v \in son[u]}(\sum_{i=1}^{m}f2[v][j] \times [ok(i,j)])

其中 ok(i,j) 表示没有 (i,j) 这个限制。总方案数就是：\sum_{i=1}^{m}f2[1][i]

接下来考虑求有一种猫粮超出数量限制的方案。可以枚举超出限制的猫粮 x，f[u][i][j] 表示在 u 点的猫粮种类是 i 一共选了 j 个种类 x 的猫粮方案数。有转移：

f'[u][i][j+l]=\sum_{v \in son[u]}f[u][i][j] \times f[v][k][l] \times [ok(i,k)]

总的不合法的方案就是：\sum_{i=c[i]+1}^{n} \sum_{j=1}^{m} f[1][j][i]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 55;
const int mod = 353442899;
int n,m,t,c[N];
vector<int> E[N];
bool vis[N][N];
int f[N][N][N],g[N][N],x,ans,sz[N];
//f[u][i][j] 表示在u点的猫粮种类是i一共选了j个种类x的猫粮
inline void dfs(int u,int fa){
    sz[u] = 1;
    for(int i = 1;i <= m;i ++)f[u][i][i == x] = 1;
    for(int v : E[u]){
        if(v == fa)continue;
        dfs(v,u);
        memset(g,0,sizeof(g));
        for(int o = 1;o <= m;o ++){
            for(int i = 1;i <= m;i ++){
                if(vis[o][i])continue;
                for(int j = 0;j <= sz[u];j ++){
                    for(int k = 0;k <= sz[v];k ++)
                        g[o][j + k] += f[u][o][j] * f[v][i][k] % mod;
                }
            }
        }
        sz[u] += sz[v];
        for(int i = 1;i <= m;i ++)
            for(int j = 0;j <= sz[u];j ++)f[u][i][j] = g[i][j] % mod;
    }
}
//g[u][i]表示在u点猫粮种类是i的方案数
int f2[N][N];
inline void dfs2(int u,int fa){
    for(int i = 1;i <= m;i ++)f2[u][i] = 1;
    for(int v : E[u]){
        if(v == fa)continue;
        dfs2(v,u);
        for(int i = 1;i <= m;i ++){
            int cnt = 0;
            for(int j = 1;j <= m;j ++)if(!vis[i][j])
                cnt += f2[v][j];
            f2[u][i] = f2[u][i] * cnt % mod;
        }
    }
}
signed main(){
    cin >> n >> m >> t;
    for(int i = 1;i <= m;i ++)cin >> c[i];
    for(int i = 1;i < n;i ++){
        int u,v;
        cin >> u >> v;
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for(int i = 1;i <= t;i ++){
        int x,y;
        cin >> x >> y;
        vis[x][y] = 1;
    }
    //枚举超出数量限制的猫粮种类
    for(x = 1;x <= m;x ++){
        memset(f,0,sizeof(f));
        dfs(1,0);
        for(int k = 1;k <= m;k ++)
            for(int j = c[x] + 1;j <= n;j ++)ans -= f[1][k][j];
        ans %= mod;
    }
    dfs2(1,0);
    for(int i = 1;i <= m;i ++)ans += f2[1][i];
    ans %= mod;ans = (ans + mod) % mod;
    cout << ans;
    return 0;
}