题解：P3577 [POI2014] TUR-Tourism

lupengheyyds · 2024-11-02 11:30:49 · 题解

P3577 [POI2014] TUR-Tourism

可能很多人看到这道题既可以从父亲更新到儿子，又可以从儿子更新到父亲的时候，很多人都跟我一样是这样的：

于是这里分享一下我的一种思考。

直径 \le 10，可以先求出 DFS 生成森林，这样树高不超过 10 且没有横叉边，我们使返祖边是通过祖先限制后代，于是可以记录节点到根节点所有点的状态，共三种：

首先求出这个树的欧拉序，下文中 x_i 表示欧拉序第 i 个位置的节点编号。

令 f_{i,j} 表示考虑欧拉序前 i 个位置，x_i 到根的路径上的状态为 j 时的最小代价。由于一个节点需要受到其祖先节点状态的限制，所以每个节点的决策（选或不选）应该在其欧拉序中第一个位置进行。 考虑 i-1\to i 的一次转移，假设之前的状态为 s=j。

• 如果 x_{i-1}=fa_{x_i} 也就是说这是一条向下的边，考虑 x的的决策：

  • 如果 x_i 选择，那么当前节点的状态无论如何都是 0，考虑与 x_i 有边的一个祖先 z：

  • 如果 z 的状态为 0,2，则 s 不作改变。

  • 如果 z 的状态为 1，则 s\to s+2\times 3^{dep_z}。

  • 如果 x_i 不选择，那么看当前节点有没有被自己的祖先覆盖：

  • 如果没覆盖，则 s\to s+3^{dep_{x_i}}。

  • 如果被覆盖，则 s\to s+2\times 3^{dep}。

  最后让 dp_{i,s}\leftarrow dp_{i-1,j}。

• 如果 fa_{x_{i-1}}=x_i，也就是说这是一条向上的边，直接 dp_{i,j}=\min\{dp_{i-1,j},dp_{i-1,j+2\times 3^{dep_{x_{i-1}}}}\}。

最后一棵树的答案就是 \min\{dp_{2n-1,0},dp_{2n-1,2}\}，最终答案就是所有树的答案之和。

其实我们没有必要真正的把欧拉序列求出来，直接在 DFS 遍历的过程中求一下就行了，复杂度 \mathcal O(3^hm)，但是很多状态是不必要的，卡卡常就过了。