小圆可爱！|【题解】P12002 吃猫粮的玉桂狗

Starrykiller · 2025-03-29 18:26:02 · 题解

令 u 点权为 a_u。问题转化为，\forall u,v（v\in \mathrm{son}(u)），都有 (a_u,a_v) 没有被 ban，且每个点权 i 的出现次数都不大于 c_i 的方案数。

考虑关键性质：c_i\ge n/2。这意味着，若 i 的出现次数超出了限制，别的点权的出现次数必然合法，考虑枚举这个不合法的容斥（Emiya 家今天的饭）。

首先总方案数是好算的：令 f(u,i) 表示 a_u=i 的方案数，合并就是 f(u,i)\gets f(u,i)\prod_{(i,j)\text{ is valid}} f(v,j)。

枚举点权 x 的出现次数超出限制，只需要再记一维 j，表示 x 的出现次数。这样合并就是一个树上背包，时间复杂度 \Theta(m\cdot n^2m^2)=\Theta(n^2m^3)，可以通过。

鲜花：原本此题的数据范围是 n,m\le 100，我验题的时候写了个暴力过了，才得知实际数据范围。