树形限制的排列生成dp

对于这类树形限制的生成排列的题记录两种不同的做法

\(\color{blue}\textbf{[例题]}\)

第一种方法(暴暴暴暴暴力dp)
P4099 [HEOI2013]SAO
P3757 [CQOI2017]老C的键盘

第二种方法(容斥+dp)
P5405 [CTS2019] 氪金手游

题面

生成一个大小为 n 的排列，满足 n-1 条形如 p[x]>p[y] 的限制，且这些限制恰好能构成一棵树，求方案数。

第一类做法

这种做法比较垃圾，处理不了带权生成排列
设 f[i][j] 表示在只考虑 i 的子树内的限制，生成了一个大小为 siz[i] 的排列，且在排列中树根 i 是排列中第 j 个，满足这个要求的排列有多少个，然后就是暴力转移，每次考虑不断加入子树，然后就像插数一样把别的子树的排列插到原排列上，系数就是个组合数什么的，前缀和优化一下就是 \(O(n^2)\) 的。没错，很暴力。

第二类做法（容斥）

回到刚才那个问题，假如树形结构是一棵内向树（外向树亦可）那么会怎么样？就意味着树根 i 在其子树构成的排列中一定是第一个，而子树之间没有限制直接组合数乱插就行了，十分的好算。考虑不是内向树，那么在合并子树的时候我要满足若干个树根 i 与其儿子 v=son[i] 之间的限制，直接开始大力容斥，我只关心那些从 i 指向儿子的边，称之为反向边，我反过来就变成了:
①一定违反了这个限制
②可能违反了这个限制（就是把这条边删掉）
这样直接容斥就变成了至多 \(O(2^{n-1}n)\) 的，但是可以考虑优化，我容斥的话我关心的容斥系数实际上只与我强制多少违反了这个限制的个数有关，那么我 dp 的时候再开一维来记录我目前有多少个限制是强制违反的，这样是 \(O(n^3)\) 的，但是再仔细思考一下，我 dp 的时候如果强制违反限制，那么就是给我当前的 dp 值乘以一个 \(-1\) ，因此我就不用多记一维，我可以在转移的时候直接在 dp 数组上操作，这个真的非常神奇，时间复杂度变成了 \(O(n^2)\) ，而且还能处理带权生成排列，每个带权只在其作为根的地方插进去即可，非常的 useful