题解：AT_arc179_d [ARC179D] Portable Gate

快乐的大童 · 2024-06-10 22:35:48 · 题解

题意简述

有一棵树 n 个点，你有一个门，你现在从一个你选定的点开始走，目标是所有点都至少访问一次。每次你可以选择：

• 经过一条树边走到相邻点，花费 1。
• 将门放在当前点。
• 将自己传送到门所在的点。

求最小花费。n\le 2\times10^5。

分析

先考虑根（出发点）固定怎么做。

由于放门没有任何代价，我们可以视为在正常行走时随身把门也带上。正常情况下我们肯定是访问完一个子树后进入另一个子树继续访问，而显然门的位置一定在子树的祖先上，所以子树之间的花费相互独立。

再发现一个比较重要的性质：一个子树内若门在子树祖先上，则传送技能仅会使用至多一次。

证明：若使用两次以上，证明该点和门点之间的边要走两遍，那么我们将门放在该点上，该点和门点之间的边也要走两遍，但遍历该子树的代价不会变劣。

由此考虑树形 dp，设 f_{i,0/1} 表示走完 i 子树内的所有点，是否需要返回根节点的最小花费（注意原题中也无需返回出发点），转移：

• 令 g_u 表示 u 子树中离 u 距离最远的点的距离。
• 令 t_u=2\cdot(siz_u-1)-g_u，表示在走 u 子树时门在 u 的祖先上时走完 u 子树且不返回根节点的最小花费，2\cdot(siz_u-1) 表示走完 u 子树且返回根节点的最小花费，若不返回根节点，肯定要尽可能的少走，我们贪心的选离 u 和离其最远的点这条链少走一遍，则减掉 g_u。

再考虑根不固定的情况，有了树形 dp 式子，直接换根即可。

简述换根流程：

• 计算以该点为根时的答案。
• 枚举子树，删掉子树的贡献（若是取最值可以同时保留次值，若最值是该子树贡献的则减掉最值加上次值），递归进子树。

  代码

  注意代码中的 t_x 和题解中的 t_x 定义有略微不同。

https://atcoder.jp/contests/arc179/submissions/54430907

upd on 2024-11-12：修改了两处笔误。

upd on 2024-11-12：第一次修改又改出一个错误。我是什么唐诗 /ll