\(O(m*n*2^n)\) 很好做，但是本题有更优秀的做法：在此记录复杂度 \(O(n*2^n)\) 的做法。
考虑从后往前 dp，设 dp 状态 \(f_{s,0/1}\) 分别表示在填了 \(s\) 集合内的树边和必须填的非树边的方案数/价值总和。
先预处理出辅助数组 \(g_s\) 表示如果填了 \(s\) 集合内的树边，那么有多少条边必须填（有些非树边必须填在树边之后）。具体地，预处理 \(g_s\)，可以求出有多少非树边所覆盖的集合的补集包含了 \(s\) 的补集，非树边中只有这些边是可以在 \(s\) 集合之前填的。
预处理出 \(g_s\) 之后就可以考虑怎么转移了，方案数比较简单，枚举 \(s\) 集合中这次填的是哪条边，从集合 \(t\) 转移过来。原本只有填了 \(g_t\) 条边，现在填了 \(g_s\) 条边，新增了一条树边和 \(g_s-g_t-1\) 条非树边，其中树边一定是填在最前面的，而非树边就可以在剩下的 \(g_s\) 个位置随便填。于是这一步的方案数就是 \(A_{g_s-1}^{g_s-g_t-1}\)。综上，转移就是： \(f_{s,0}=\sum_t f_{t,0}*A_{g_s-1}^{g_s-g_t-1}\)。
价值总和比较难算，如果在开头加一条树边，那么所有树边的排名都会+1，对于一个方案的贡献就是 \(popcount(s)\)。然后考虑要加的那 \(g_s-g_t-1\) 条非树边，假设一条一条依次加入，如果现在已经填了 \(x\) 条边，价值之和为 \(y\)，那么新加进去的这条边就有 \(x+1\) 个位置可以填，而加进去这条边以后，可能有一些已经加进去的树边排名+1，假设原本这些树边的排名分别是 \(a_1,a_2,\dots,a_{|T|}\) 那么对于排名 \(a_i\) 的边，新加进去的这条边只有在填在开头的 \(a_i\) 个位置才会使其排名+1，所以左右方案对排名的贡献就为 \(\sum a_i\)，结果发现这个就是价值之和 \(y\)。总结一下：在已经填了 \(x\) 条边，价值之和为 \(y\) 的基础上加入一条新的边，\(y'=(x+1)*y+y=(x+2)*y\)，其中 \((x+1)*y\) 是继承之前的贡献，\(y\) 是新填的这条边所有方案的贡献。而现在要加入 \(g_s-g_t-1\) 条非树边，那么：\(f_{s,1}=f_{t,0}*popcount(s)+f_{t,1}*\prod_{x=g_t}^{g_s-2}(x+2)\)。
预处理阶乘即可 \(O(1)\) 转移。
标签：树边,题解,20221115,Tree,集合,加进去,条边,非树边,预处理 From： https://www.cnblogs.com/william555/p/16893734.html