「Codeforces 599E」Sandy and Nuts
题意
有一棵\(n\)个节点的以1为根的树，有\(m\)条边已知，并且有\(q\)个限制\(a_i,b_i,c_i\)，需要满足\(\mathrm{LCA}(a_i,b_i)=c_i\)。求满足条件的树的数量。
\(m< n\le 13,q\le 100\)。
题解
树形状压DP。DP状态很显然，\(dp_{u,mask}\)表示以\(u\)为根，由\(mask\)这些点组成的子树的方案数。\(mask\)是一个二进制状态。
为方便讨论，以下题解和代码节点编号从\(0\)开始。
转移方程
\[dp_{u,mask}=\sum dp_{v,submask}\times dp_{u,mask\oplus submask}\]
\(\oplus\)表示的是异或(\(xor\))运算。
但是，我们直接枚举\(v,submask\)会有重复，例如一棵二叉树，根为\(root\)，左右儿子分别为\(leftson,rightson\)。当枚举\(v=leftson\)时会计算这棵树，\(v=rightson\)时又会计算这棵树，就会出现重复。
所以，我们规定一个点\(pos\in mask\ (pos\ne u)\)，强制\(pos\)在\(submask\)中才能转移。
转移条件
题目中有两种限制条件，分别为边和\(\mathrm{LCA}\)。
- 对于\(\mathrm{LCA}\)的限制： 1.1. 对于限制\((a,b,c)\)，如果\(c=u\)，但是\(a,b\in submask\)，那么\(\mathrm{LCA}\)一定不为\(c\)，不满足条件。 1.2. 对于限制\((a,b,c)\)， 如果\(c\in submask\)，但\(a,b\)中有至少一个不在\(submask\)中，则\(\mathrm{LCA}\)一定不为\(c\)，不满足条件。
- 对于边的限制： 2.1. 对于边\((x,y)\)，如果\(x,y\ne u\)，但是\(x,y\)其中一个在\(submask\)中，另一个不在，则这条边不可能在树上，不满足条件。 2.2. 如果\(u\)与\(i\)有边且\(i\in submask\)的\(i\)的数量大于1，则不可能有满足条件的树，不满足条件。
在2.2中，如果这样的\(i\)的数量等于1，则转移时\(v\)不用枚举，\(v\)只能是那个\(i\)。否则\(v\)需要在\(submask\)中枚举。
关于复杂度
子集枚举可以用for (register int submask = mask; submask; submask = (submask - 1) & mask)。
此时复杂度并不是\(O(4^n)\)，而是\(O(3^n)\)，因为每次枚举到的\(submask\)一定是\(mask\)的子集。状态数为\(3^n\)。
因为此时\(n\)个数有三种状态：不在\(mask\)中，在\(mask\)但不在\(submask\)中，在\(submask\)中。所以是\(3^n\)。
所以复杂度为\(O(3^nn(n+q+m))\)。
观察代码可以发现这个复杂度非常不满，很多状态和子集是没用的。加上CF的评测机速度，还是可以过的。
代码
Code 实测93ms
1 |
|
