思路解析
这道题的本质是一棵树上选择两种“轰炸”方式，要求最终的总花费最大。
- 操作 1：炸一个城市，花费 x。
- 操作 2：炸整个连通块，花费 y。
目标：在把所有城市都摧毁的前提下，让花费尽可能大。
P3623.第3题-轰炸机
题目内容
在遥远的星球上有T国与K国，其中T国是由n座城市(编号为1~n)和n−1条双向道路组成的，保证任意两座城市之间互通。
某天，强大的K国决定轰炸T国的所有城市，K国可以进行以下两种操作;
-
选择一个尚未轰炸的城市，花费x财力，将该城市本身、所有与之直接相连的道路，一并轰炸。
-
选择一个尚未轰炸的城市，花费y财力，将该城市所在的由尚未轰炸的城市与道路构成的连通块内，所有城市和道路，一并轰炸。
每种操作可反复使用，直至所有城市被轰毁。为了彰显财力，K国希望使用最多的财力来摧毁所有城市，请你计算并输出这个最大财力消耗。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤104)代表数据组数，每组测试数据描述如下:
第一行输入三个整数n,x,y(1≤n≤2×105;1≤x,y≤109)，分别表示城市数量和两种轰炸操作的财力消耗;
接下来 n−1 行,每行输入两个整数 u,v(1≤u,v≤n;u=v)，表示道路两端的城市编号。
除此之外，保证单个测试文件的n之和不超过2×105。
输出描述
对于每组测试数据，新起一行，输出一个整数，表示最大财力消耗。
样例1
输入
2
3 1 3
1 2
2 3
5 2 1
1 2
2 3
3 4
4 5
输出
7
10
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
