两个朋友,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