题目内容

在一棵由 $n$ 个处理单元和 $n-1$ 条链路组成的树形网络中，初始时每个处理单元均处于“待清理”状态。现在需要清理所有单元及其链路，允许反复执行以下两种操作：

• 单点清理：选择一个待清理的处理单元，花费 $x$ 代价，将该单元以及所有与之直接相连的链路一并清理。
• 区域清理：选择一个待清理的处理单元，花费 $y$ 代价，将该单元所在的、由待清理单元和链路构成的连通块中的所有单元和链路一并清理。 每次操作完成后，被清理的单元和链路将不再参与后续操作。目标是通过选择操作顺序，使得清理全部单元和链路的总代价达到最大。请计算这个最大总代价。

约束：输入包含多组测试数据。第一行一个整数 $T$（$1 \le T \le 10^4$）表示数据组数。每组数据中，处理单元数量 $n$ 不超过 $2 \times 10^5$，代价 $x, y$ 均不超过 $10^9$。保证所有数据组的 $n$ 之和不超过 $2 \times 10^5$。

输入描述

第一行输入一个整数 $T$，表示测试数据组数。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写