第3题-轰炸机

题目

在遥远的星球上有 T 国与 K 国，其中 T 国是由 $n$ 座城市（编号为 $1 \sim n$）和 $n - 1$ 条双向道路组成的，保证任意两座城市之间互通。某天，强大的 K 国决定轰炸 T 国的所有城市，K 国可以进行以下两种操作：

1. 选择一个尚未轰炸的城市，花费 $x$ 财力，将该城市本身、所有与之直接相连的道路，一并轰炸。
2. 选择一个尚未轰炸的城市，花费 $y$ 财力，将该城市所在的由尚未轰炸的城市与道路构成的连通块内，所有城市和道路，一并轰炸。

每种操作可反复使用，直至所有城市被轰毁。为了彰显财力，K 国希望使用最多的财力来摧毁所有城市，请你计算并输出这个最大财力消耗。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，每组测试数据描述如下：
第一行输入三个整数 $n, x, y$，分别表示城市数量和两种轰炸操作的财力消耗；
接下来 $n - 1$ 行每行输入两个整数 $u, v$，表示道路两端的城市编号。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示最大财力消耗。

（回忆版无样例，可直接用代码自测）

思路

若 $x \ge y$：全用操作 1，答案 $n \cdot x$（操作 2 至少覆盖一个城市，不划算）。

若 $x < y$：先把每个城市都按操作 1 计入花费 $n \cdot x$，再尽量把一些城市「升级」为操作 2（每升级一个多花 $y - x$）。能够用操作 2 处理的城市在树上构成一个独立集（相邻城市若都被单独升级会互相破坏连通块结构），因此最多升级的个数为树的最大独立集（MIS），答案为 $n \cdot x + \text{MIS} \cdot (y - x)$。MIS 用树形 DP：dp1[u] = Σ dp0[v] + 1（选 u）、dp0[u] = Σ max(dp1[v], dp0[v])（不选），迭代写法用栈序 + 逆序转移避免递归深度问题。

代码

import sys

def main():
    it = iter(sys.stdin.read().strip().split())
    t = int(next(it))

    for _ in range(t):
        n, x, y = int(next(it)), int(next(it)), int(next(it))
        g = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            u, v = int(next(it)), int(next(it))
            g[u].append(v)
            g[v].append(u)

        if x >= y:
            print(x * n)
            continue

        parent = [0] * (n + 1)
        root = 1
        st = [root]
        order = []
        while st:
            u = st.pop()
            order.append(u)
            for v in g[u]:
                if v == parent[u]:
                    continue
                parent[v] = u
                st.append(v)

        dp0, dp1 = [0] * (n + 1), [0] * (n + 1)
        for u in reversed(order):
            for v in g[u]:
                if v == parent[u]:
                    continue
                dp1[u] += dp0[v]
                dp0[u] += max(dp1[v], dp0[v])
            dp1[u] += 1
        mis = max(dp0[root], dp1[root])
        ans = n * x + mis * (y - x)
        print(ans)

if __name__ == "__main__":
    main()

来源：25秋招笔试真题-小红书0907（知乎专栏）（回忆版）