P3577 [POI2014] TUR-Tourism
可能很多人看到这道题既可以从父亲更新到儿子,又可以从儿子更新到父亲的时候,很多人都跟我一样是这样的:
于是这里分享一下我的一种思考。
直径 \(\le 10\),可以先求出 DFS 生成森林,这样树高不超过 \(10\) 且没有横叉边,我们使返祖边是通过祖先限制后代,于是可以记录节点到根节点所有点的状态,共三种:
-
\(0\):这个点选择了
-
\(1\):这个点没选择且相邻点没有选择(没被覆盖)
-
\(2\):这个点没选择且相邻点有选择(被覆盖)
首先求出这个树的欧拉序,下文中 \(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)\),但是很多状态是不必要的,卡卡常就过了。
标签:状态,dep,TUR,选择,欧拉,P3577,Tourism,节点,dp From: https://www.cnblogs.com/lupengheyyds/p/18521932