题解

思路

把树按根节点 $1$ 定向。设 $siz_u$ 为 $u$ 的子树大小，$dp_u$ 表示当感染刚到达 $u$ 时， 在其子树中最多能拯救多少个顶点。

若 $u$ 没有孩子，不能拯救任何顶点。若只有一个孩子 $v$，立刻删除 $v$，则 $v$ 本身不计入获救， 但它的其余 $siz_v-1$ 个后代全部与感染隔离。若有两个孩子 $x,y$，这一轮可以删除其中一个孩子； 被删除孩子的其他后代全部获救，感染只进入另一个孩子，再按对应的 $dp$ 最优处理。

做法

迭代建立父子关系和遍历顺序，逆序计算子树大小。按孩子数分别使用上述三种转移，最后输出根节点的 $dp$ 值。

正确性证明

感染到达 $u$ 后，下一次传播前至多删除一个未感染顶点。删除某个孩子的后代不如直接删除该孩子： 直接删除孩子会同时阻断更大的子树，且删除顶点同样只损失一个。因此存在最优策略只考虑删除孩子。

没有孩子时转移显然正确。只有一个孩子时，删除它可立即隔离全部后代，任何不删除它的策略都会让 感染进入该子树，不能获得更多。两个孩子时，一轮只能阻断一个子树；选择阻断 $x$ 后，$x$ 的 $siz_x-1$ 个后代获救，另一棵子树的最优收益恰为 $dp_y$，反之同理。取两者最大覆盖所有最优选择。 由子树后序归纳，根节点状态给出全局最优答案。

复杂度

每个顶点和每条边只处理常数次，单组时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。