新高一暑假第一期集训恢复性训练【DP版块】（补）

新高一暑假第一期集训恢复性训练【DP版块】（补）

A. [CEOI2017] MUSEUM

树形 dp。

设 \(f_{i, j},g_{i, j}\) 表示以 \(i\) 为根的子树中，访问了 \(j\) 个点，回到 \(i\) 和不必回到 \(i\) 的代价。

转移的时候做类似于背包一样的东西。

时间复杂度 \(\Theta(n^2)\)。

B. [ABC207F] Tree Patrolling

设 \(f_{i, j, 0/1/2}\) 分别表示以 \(i\) 为根的子树保护了 \(j\) 个点的方案数，未放置自己，且没被子节点保护；未放置自己，但被子节点保护；放置了自己 这三种情况。

转移从所有子节点的状态转移过来比较好想。然后主要有一点就是会存在增加新节点的情况。

1. 自己没有放置，但是被子节点覆盖了。
2. 子节点没有放置，但是被父节点覆盖了。

转移是树型背包。理论上时间复杂度为 \(\Theta(n^3)\)。

优化：

1. 动态维护 \(size\)，这样就可以保证每对点都在 LCA 处合并了一次 \(\rightarrow\) \(\Theta(n\log n)\)。
2. 为了去除重复记录方案的情况，每次转移开个空数组记录答案。