给一棵树，每个节点是一座城市，每次有两种操作，1炸掉一座城市花费x，2炸掉一座城市及其所在的联通块内...

Question

给一棵树，每个节点是一座城市，每次有两种操作，1炸掉一座城市花费x，2炸掉一座城市及其所在的联通块内的所有城市，花费y，求最大花费

Answer 1

下面这题的关键在于：
先用若干次“单点爆破”（操作1，费用 x）删掉一部分点，使树被切成若干联通块；最后对每个剩余联通块各用一次“整块爆破”（操作2，费用 y）。要最大化总费用。

把被单点删掉的点集记作 $S$ 。删完 $S$ 后剩下的联通块数 $C$ 满足（树上恒等式）：

C \;=\; 1 + |\delta(S)| + e_S - |S|

其中 $|\delta(S)|$ 是跨越割 $S$ 与补集的边数， $e_S$ 是 $S$ 内部的边数。
于是总费用：

\text{cost}(S)= |S|\cdot x + C\cdot y = y \;+\; \underbrace{\big(|S|\cdot x + y\cdot|\delta(S)| - y\cdot c_S\big)}_{F(S)}

这里用到了 $e_S = |S| - c_S$ （树上 $S$ 的诱导子图是森林，边数 = 点数 − 组件数）， $c_S$ 是 $S$ 内部连通分量数。
因此问题化为最大化

F(S)= |S|\cdot x + y\cdot|\delta(S)| - y\cdot c_S,

最后答案再加一个常数 $+y$ （当 $S$ 取遍全体点时， $C=0$ ，这个常数会和 $-y$ 抵消，仍然正确）。

树形 DP 做法（O(n)）

任选根 $r$ ，对每个点 $u$ 定义三种状态（值均为“贡献的 $F$ ”而非总 cost）：

$f_0(u)$ ： $u\notin S$ ；
$f_1(u)$ ： $u\in S$ 且与父亲同属一个 $S$ 内部连通块（不新开块）；
$f_2(u)$ ： $u\in S$ 且其父 $\notin S$ （在 $u$ 处新开一个 $S$ 内部连通块，需支付 $-y$ 的“开块惩罚”）。

转移（孩子集合为 $\text{ch}(u)$ ）：

若 $u\notin S$ ：
$f_0(u)= \sum_{v\in \text{ch}(u)} \max\Big( \;f_0(v),\; f_2(v)+y\;\Big)$
解释：孩子 $v$ 若进 $S$ ，由于父不在 $S$ ，必须从 $v$ 开新块（ $f_2$ 含 $-y$ ），同时边 $(u,v)$ 被切， $|\delta|$ 增 1 给 $+y$ ，两项在数值上“抵一部分”，但需分别计入。
若 $u\in S$ 且与父同块：
$f_1(u)= x \;+\; \sum_{v\in \text{ch}(u)} \max\Big( \;f_1(v),\; f_0(v)+y\;\Big)$
解释： $u$ 取入给 $+x$ 。孩子若不取入，边被切给 $+y$ ；若取入，则必须与 $u$ 相连同块（选 $f_1(v)$ ）。
若 $u\in S$ 且父不在 $S$ ：
$f_2(u)= x - y \;+\; \sum_{v\in \text{ch}(u)} \max\Big( \;f_1(v),\; f_0(v)+y\;\Big)$
解释：在 $u$ 新开一个 $S$ 内部块，先付 $-y$ ，点费 $+x$ ，孩子转移与 $f_1$ 相同。

根没有父节点，因此最终

F^*=\max\big(f_0(r),\; f_2(r)\big), \qquad \text{答案} = y + F^*.

边界检查

取 $S=\varnothing$ ：DP 会得到 $F^*=0$ ，答案 $=y$ （一次整块爆破整个树）。
取 $S=V$ ：DP 会得到 $F^*=n\cdot x - y$ ，答案 $=n\cdot x$ （全用单点爆破）。

伪代码

text
build tree, root at 1
dfs(u, parent):
  f0 = 0
  f1 = x
  f2 = x - y
  for v in children(u):
    dfs(v, u)
    f0 += max( f0[v], f2[v] + y )
    f1 += max( f1[v], f0[v] + y )
    f2 += max( f1[v], f0[v] + y )
  save f0[u], f1[u], f2[u]

dfs(root, 0)
answer = y + max( f0[root], f2[root] )
print(answer)

时间复杂度 $O(n)$ ，空间 $O(n)$ 。
这套转移不需要特判 $x$ 与 $y$ 的大小关系，统一适用，自动给出“全单点”“全整块”以及“两者混合（先切点再整块）”中的最优策略。

给一棵树，每个节点是一座城市，每次有两种操作，1炸掉一座城市花费x，2炸掉一座城市及其所在的联通块内...

سؤال

الفكرة

Maximizing destruction costs

Maximizing destruction through partitioning

Maximizing total cost strategy

Adjusting removal strategy

Calculating components after node removal

Optimizing node selection

Optimizing dynamic programming solution

الإجابة

树形 DP 做法（O(n)）

边界检查

伪代码

مشاركة هذا السؤال والجواب