自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 23:12:01，当前版本为作者最后更新于2025-04-01 17:04:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

又拿这个套路炒了一波冷饭。看赛时榜好像大家还是不太会，所以希望这个题能对这个套路有一定普及作用。

猜你想搜：

• P5664 Emiya 家今天的饭
• P8202 染色
• CF1487G String Counting

考虑这个每种猫粮的数量多于一半有什么用：在满足位置限制（所有的 $(a_i, b_i)$ 对）时，任意不合法方案都只有一种猫粮超出数量限制。因为如果有两种猫粮 $x,y$ 超出了限制，假设分别放了 $w_1, w_2$ 个，那么有 $w_1 > c_x \geq \lfloor\frac{n}{2}\rfloor$，$w_2>c_y \geq \lfloor\frac{n}{2}\rfloor$，则 $w_1 + w_2 > n$。而所有猫粮加起来只会选 $n$ 个，所以这种情况不会存在。

可以考虑枚举那个超限制的猫粮 $x$，那么其它猫粮都可以随便选，假设种类 $x$ 的猫粮超限制的方案数是 $A(x)$，在不考虑猫粮数量限制时的方案数是 $S$，则可以容斥一下合法方案数就是 $S - \sum_{x= 1}^m A(x)$。考虑计算 $A(x)$。

注意到我们关于位置的限制（所有的 $(a_i, b_i)$ 对）其实等价于：以 $1$ 为根的树，不存在任何父亲-孩子对使得父亲的猫粮是 $a_i$，孩子的猫粮是 $b_i$。考虑枚举超限制的猫粮种类 $x$，进行树形 DP：$f_{u,i,j}$ 表示以 $u$ 为根的子树，$u$ 的猫粮种类是 $i$，且种类为 $x$ 的猫粮已经放了 $j$ 个的方案数。可以进行树上背包转移：

枚举 $u$ 的孩子 $v$，设 $u$ 当前已经转移的孩子放了 $i$ 个猫粮 $x$，$v$ 这个孩子选了 $j$ 个猫粮 $x$，$u$ 的猫粮种类是 $h$，$v$ 的猫粮种类是 $k$，当前已转移的孩子的状态放在 $f'$ 里，有：

$$f(u,h,i+j) \leftarrow \sum_{k = 1}^m (f(v,k,j) \times f'(u, h,i) \times[\mathrm{ok}(h,k)]) $$

这里当 $(h,k)$ 这个限制不存在时，$[\mathrm{ok}(h,k)]=1$，否则为 $0$。

如果不理解树上背包转移可以去看代码。

如果把第二维拿掉，那么这个 dp 是在做标准树上背包。所以上式是在树上背包的基础上枚举了 $h$ 和 $k$ 两维。标准树上背包的复杂度是 $O(n^2)$，因此上面这个 dp 的复杂度是 $O(n^2m^2)$。算上我们外面枚举的不合法的猫粮种类 $x$，总的复杂度是 $O(n^2m^3)$。

那么 $A(t) = \sum_{i= 1}^m \sum_{j = c_{t} + 1}^nf(1,i,j)$

对 $S$（总方案数）的计算也是简单的，直接把记录猫粮 $x$ 的数量一维删掉即可。

$$g(u,h) \leftarrow g'(u,h) \times \sum_{k = 1}^m g(v,k)\times[\mathrm{ok}(h,k)] $$

减一下就做完了。

注意树上 DP 的过程里不要对最后一维有无效的枚举，否则复杂度是不对的。

#include <bits/stdc++.h>

const int p = 353'442'899;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, t;
  std::cin >> n >> m >> t;
  std::vector<int> c(m + 1);
  for (int i = 1; i <= m; ++i) std::cin >> c[i];
  std::vector e(n + 1, std::vector<int>()), lim(m + 1, std::vector<int>(m + 1, 0));
  for (int i = 1, u, v; i < n; ++i) {
    std::cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  for (int u, v; t; --t) {
    std::cin >> u >> v;
    lim[u][v] = 1;
  }
  std::vector g(n + 1, std::vector(m + 1, 0));
  auto Dfs = [&](auto &&dfs, int u, int pre) -> void {
    for (int col = 1; col <= n; ++col) g[u][col] = 1;
    for (auto v : e[u]) if (v != pre) {
      dfs(dfs, v, u);
      for (int curCol = 1; curCol <= m; ++curCol) {
        int sum = 0;
        for (int childCol = 1; childCol <= m; ++childCol) if (!lim[curCol][childCol]) {
          (sum += g[v][childCol]) %= p;
        }
        g[u][curCol] = 1ll * g[u][curCol] * sum % p;
      }
    }
  };
  Dfs(Dfs, 1, 0);
  int ans = 0;
  for (int col = 1; col <= m; ++col) {
    (ans += g[1][col]) %= p;
  }
  for (int tarCol = 1; tarCol <= m; ++tarCol) {
    std::vector f(n + 1, std::vector(m + 1, std::vector(n + 1, 0)));
    std::vector<int> sz(n + 1);
    auto dfs = [&](auto &&dfs, int u, int pre) -> void {
      sz[u] = 1;
      for (int curCol = 1; curCol <= m; ++curCol) {
        f[u][curCol][curCol == tarCol] = 1;
      }
      for (auto v : e[u]) if (v != pre) {
        dfs(dfs, v, u);
        for (int curCol = 1; curCol <= m; ++curCol) {
          std::vector curf(sz[u] + sz[v] + 1, 0);
          for (int childCol = 1; childCol <= m; ++childCol) if (!lim[curCol][childCol]) {
            for (int lsh = 0; lsh <= sz[u]; ++lsh) {
              for (int rsh = 0; rsh <= sz[v]; ++rsh) {
                curf[lsh + rsh] += 1ll * f[v][childCol][rsh] * f[u][curCol][lsh] % p;
                curf[lsh +rsh] %= p;
              }
            }
          }
          for (int i = 0; i <= sz[u] + sz[v]; ++i) f[u][curCol][i] = curf[i];
        }
        sz[u] += sz[v];
      }
    };
    dfs(dfs, 1, 0);
    for (int i = c[tarCol] + 1; i <= n; ++i) {
      for (int col = 1; col <= m; ++col) {
        ans -= f[1][col][i];
        ans = (ans + p) % p;
      }
    }
  }
  std::cout << ans << std::endl;
}

不知道下次把这个精品小套路掏出来扔到比赛里会是什么时间。