【解题报告】牛客挑战赛70 maimai

这个挑战赛的$F$是我出的，最后 zhoukangyang 爆标了。。。orzorz

题目链接

这个挑战赛的$F$是我出的，最后 zhoukangyang 爆标了。。。orzorz

记所有有颜色的边的属性集合 $S$ 。

首先在外层容斥，枚举 $S\in [0,2^w)$，计算被覆盖的的边中不包含 $S$ 中属性，并且没有被覆盖的边的数目恰好为 $i$ 的配对方案数。

暴力的 DP 做法是记录子树内还没有被匹配的点的数目，复杂度$O\left(n^5\right)$，不能通过。出题人特意卡了这种做法。

如果一条边没有覆盖，那么所有点对间的路径都不能经过这条边，这样我们可以把一个连通块分成两个子联通块进行求解。但是这样就要记录连通块里面所有的点，无法通过

考虑二项式反演。记 $g\left(i\right)$ 表示钦定断了 $i$ 条边（即$i$条边没有被覆盖）的方案数，$f\left(i\right)$ 表示恰好断了 $i$ 条边的方案数，注意这里的下标 $i$ 不包含一定不被覆盖的边。那么有：

$$g\left(i\right)=\sum _{j=i}^{n-1}(\frac{j}{i})f\left(j\right)\Rightarrow f\left(i\right)=\sum _{j=i}^{n-1}(-1{)}^{j-i}(\frac{j}{i})g_j$$

而 $g\left(i\right)$ 是好算的，也就是剩下的每个连通块内部任意连边的方案数的乘积

记 $h\left(n\right)$ 表示大小为 $n$ 的连通块任意连边的方案数，如果 $n$ 为奇数那么答案是 $0$，如果 $n$ 为偶数那么答案是 $(n-1)\times (n-3)\times ...\times 1$

考虑 DP。设 $dp(u,i,j)$ 表示以 $u$ 为根的子树，已经断了 $i$ 条边，连通块大小为 $j$ 的方案数。对于一条边 $(u,v,w)$ 转移式子如下：

• $dp(u,i,j)\times dp(v,i_2,j_2)\times h\left(j_2\right)\to dp(u,i+i_2+1,j)$

• 如果 $w\notin S$，$dp(u,i,j)\times dp(v,i_2,j_2)\to dp(u,i+i_2,j+j_2)$

这个 DP 的时间复杂度上界是 $O\left(n^4\right)$ 的，因此总复杂度 $O\left(2^w{n}^4\right)$ 。

但是注意到每个连通块大小都是必须偶数，因此常数极小，实测单次 DP 计算量在 ${10}^6$ 左右，链的情况可以卡满。注意要把 DP 值为 0 的状态跳过，否则无法通过

数据里面造了一些几条链并起来的情况，暴力要跑 4s 以上，std 能稳定在 0.5s 内出解。随机数据下基本卡不了。如果有人暴力冲过去了或者正解被卡常了，出题人在这里谢罪:(

考虑到打这场比赛的大佬肯定还是比较多的，如果场切这道题的大佬们有更精确的分析复杂度的方式欢迎赛后分享。

upd：F 存在 $O\left(2^w{n}^3\right)$ 的做法，具体是将DP状态的第一维看成多项式并用点值来维护。详见zhoukangyang的代码。