主要思路
狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号，然后我们每一次往上跳的时候我们都可以对这个数组进行调整，然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候，我们把对应的 neck 提取出来，然后做标记，按标号小的进行 DP。
Continue reading →狗屎状压题。
看到度数不超过 \(10\) 就知道需要状压儿子的信息。考虑处理一个 neck 数组来表示子树内节点到当前子树根下面的节点编号，然后我们每一次往上跳的时候我们都可以对这个数组进行调整，然后 DP 的时候就会比较愉快了。
处理 \(m\) 个请求的时候，我们把对应的 neck 提取出来，然后做标记，按标号小的进行 DP。
Continue reading →怎么毫无头绪啊？（wtcl）不过有一说一，题目是真的挺好。
有一种接近正解的方式是设置 DP，设 \(dp[u][i][stat]\) 为当前在点 \(u\)、编号为 \(i\) 且被用过的编号集合为 \(stat\)，然后做一个树形 DP。不难分析出这个东西的复杂度是 \(\Theta(n^3 3^n)\)。
这个肯定过不了的，考虑进行玄学优化。假设转移时能去掉第三个限制就好了。我们考虑抛弃这个第三维。抛弃之后必须要面对的一个问题就是非法状态。我们可以考虑硬点一个点集，使得整个 DP 的时候只能选点集内的编号。发现这样答案的意义是至少有 \(i\) 个重叠选择的点的方案数，所以我们可以愉快的套一个 \((-1)^{n – |S|}\) 系数就可以的出恰好为 \(0\) 个重叠选择的方案数了。
Continue reading →首先，\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况：子树根的时间戳要早于所有的子节点，所以可以考虑直接用背包的方法进行合并。如果有反向边，那么我们可以考虑进行容斥，枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。