题解 P6773 【[NOI2020]命运】

一年前写过一篇博客 [min-max 卷积](https://www.luogu.com.cn/blog/Owencodeisking/qian-tan-min-max-juan-ji) 考前看了看前年打的牛客第二场第二题，题意大概是给定一个环，每个位置的数 $\in[1,a_i]$，要求相邻位置不相等，问有多少种环满足条件。 看完想能不能把容斥+整体 dp 放到树里呢？好像 noi/noip 没考过，自己花了一个下午想了想，想不出什么好题，本想把牛客这题的树上版本放 noip 模拟赛 t3 的。 然后 noi 就出了/cy。看到这题甚是高兴，打了一个 $O(n^2)$ 验证了一下正确性就去 rush 正解了。 上面均是废话↑↑↑ ------------- 看到存在两字，第一反应是容斥。 假定我们有指定了 $k$ 条路径没有 $1$，相当于这些边赋 $0$。其他是可以任意选的，设 $k$ 条路径径的并有 $l$ 条，它对答案的贡献为 $(-1)^k\times 2^{n-1-l}$。 继而我们发现这些路径有特点，$u$ 是 $v$ 的祖先。这样就可以 dp，$f_{i,j,k}$ 表示第 $i$ 个子树，$dep>j$ 的路径已被封锁，已选 $k$ 条路径的方案数，没有限制的话 $j=n+1$。再发现选多少条路径我们并不关心，我们只关心路径的奇偶性，可以把 $-1$ 乘到 dp 数组里面。这样我们的 dp 是两维的。 转移方程: - 合并两个子树 $f'_{\min(i,j)}=\sum (f_i\times f_j)$ - 加入限制，设最大的限制深度为 $D$，没有就不执行 $f'_{1..D-1}=0,f'_D=-\sum f_{D+1..n+1},f_{D+1..n+1}$ 不变。 - 把任意选 $0/1$ 的方法乘进去，$f_{1..dep-1}$ 不变，$f_{dep..n+1}$ 每个都乘 $2$。 这样就可以拿到 $O(nm)$ 的分数（大概），不过会了 $64$ 应该就会 $100$ 了吧（雾 接下来就是对着这个 dp 优化。（建议可以去做做「PKUWC2018」Minimax） 第一条方程是 min 卷积，可以线段树合并，进入左子树的时候把右子树的答案加过来，维护乘法标记。 第二条方程需要支持区间清 $0$，区间求和。 第三条方程需要支持区间乘法。 这些都可以线段树，所以就可以在时间 $O(n\log n)$ 解决该问题。 还有，这个线段树合并是不用给空节点下传标记的，因为没有的位值在原 dp 数组是 $0$。 ------------- 下面均是废话↓↓↓ 可能是我的常数比较大，我刚开始直接暴力清零，本机 2.01s，后来加了一个最大的 $D$ 的剪枝，本机 1.78s，开个 O2 1.49s。幸好当时卡了卡常，最后好像评测最大一个点 1.81s。上次省选 d1t2 的教训铭记在心，所以，在赛场的时候如果实在卡不进时限的 1/2 也尽量卡一卡，说不定就少了一次申诉（雾 你问代码？放考场了，这辈子都不可能有的，还是等好心人发一发吧（雾