九月做题记录（距 CSP 还有 1 个月）

1. P3959 [NOIP2017 提高组] 宝藏

发现 \(n\) 是很小的，考虑状压。

我们先记录下当前的树包含了哪些节点，然后因为转移时肯定会需要经过了多少边，也就是树的深度。

我们记录 \(\text{expand(i)}\) 表示当前选的集合为 \(i\) 时，扩展一次后的集合。\(\text{road(i, j)}\) 表示选的集合为 \(i\) 时，加入 \(j\) 不考虑深度时的最小价值。\(\text{valid(i, j)}\) 表示集合 \(i\) 能否只扩展一次变为集合 \(j\)，则 \(i\) 一定为 \(j\) 的子集。对所有大小为 \(n\) 的集合，其所有子集的个数为 \(\sum\limits_{i=0}^{n} 2^iC_{n}^i\)，用二项式定理易得 \(3^n\)。即 \(\text{valid(i,j)=1}\) 的个数是不超过 \(3^n\)。转移时通过 \(\text{valid}\) 直接转移，\(\text{valid}\)可使用 vector 进行存储。

转移方程为：\(f_{i,j}=\min\limits_{\text{valid(j,k)=1}}f_{i-1,k}+(i-1)cost_{j\to k}\)。\(cost\) 显然可以直接在处理 \(\text{valid}\) 时做到。

时间复杂度：\(\mathcal{O}(m2^n+n3^n)\)。