← 返回题目列表

Codeforces · 1822/F

F. 园艺朋友

中文机器翻译题面 查看原题

两个朋友,Alisa 和 Yuki,在他们的花园里种了一棵有 $$$n$$$ 顶点的树。树是一种无向图,没有循环、循环或多重边。该树中的每条边的长度为$$$k$$$。最初,顶点 $$$1$$$ 是树的根。

Alisa 和 Yuki 种植这棵树不仅仅是为了好玩,他们还想把它卖掉。树的成本定义为树的所有顶点中从根到顶点的最大距离。两个顶点 $$$u$$$ 和 $$$v$$$ 之间的距离是从 $$$u$$$ 到 $$$v$$$ 的路径上的边长度之和。

女孩们参加了园艺课程,所以她们知道如何改造树。 Alisa 和 Yuki 可以花费 $$$c$$$ 硬币将树的根转移到当前根的邻居之一。该操作可以执行任意次数(可能为零)。请注意,树的结构保持不变;唯一的变化是哪个顶点是根。

朋友们想以最大的利润出售这棵树。利润定义为树木成本与总运营成本之间的差额。利润是树的成本减去总运营成本。

帮助女孩们找到通过对树进行任意次数的操作(可能为零)可以获得的最大利润。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例的第一行包含整数 $$$n$$$、$$$k$$$、$$$c$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k, c \le 10^9$$$) — 树中的顶点数、每条边的长度以及操作的成本。

测试用例的接下来 $$$n - 1$$$ 行包含整数对 $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$) - 图形的边缘。这些边形成一棵树。

所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——Yuki 和 Alisa 可以获得的最大利润。

示例

输入 #1

4
3 2 3
2 1
3 1
5 4 1
2 1
4 2
5 4
3 4
6 5 3
4 1
6 1
2 6
5 1
3 2
10 6 4
1 3
1 9
9 7
7 6
6 4
9 2
2 8
8 5
5 10

输出 #1

2
12
17
32