310366: CF1822F. Gardening Friends

F. Gardening Friendstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Two friends, Alisa and Yuki, planted a tree with $n$ vertices in their garden. A tree is an undirected graph without cycles, loops, or multiple edges. Each edge in this tree has a length of $k$. Initially, vertex $1$ is the root of the tree.

Alisa and Yuki are growing the tree not just for fun, they want to sell it. The cost of the tree is defined as the maximum distance from the root to a vertex among all vertices of the tree. The distance between two vertices $u$ and $v$ is the sum of the lengths of the edges on the path from $u$ to $v$.

The girls took a course in gardening, so they know how to modify the tree. Alisa and Yuki can spend $c$ coins to shift the root of the tree to one of the neighbors of the current root. This operation can be performed any number of times (possibly zero). Note that the structure of the tree is left unchanged; the only change is which vertex is the root.

The friends want to sell the tree with the maximum profit. The profit is defined as the difference between the cost of the tree and the total cost of operations. The profit is cost of the tree minus the total cost of operations.

Help the girls and find the maximum profit they can get by applying operations to the tree any number of times (possibly zero).

Input

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains integers $n$, $k$, $c$ ($2 \le n \le 2 \cdot 10^5$; $1 \le k, c \le 10^9$) — the number of vertices in the tree, the length of each edge, and the cost of the operation.

The next $n - 1$ lines of the test case contain pairs of integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) — the edges of the graph. These edges form a tree.

The sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the maximum profit that Yuki and Alisa can get.

ExampleInput

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

Output

2
12
17
32

题目大意：
Alice和Yuki在他们的花园里种了一棵有n个顶点的树，树是一个没有环、自环或多条边的无向图。树中的每条边都有长度k。最初，顶点1是树的根。

Alice和Yuki种植这棵树不仅仅是为了好玩，她们还想要出售它。树的成本定义为从根到一个顶点的最大距离，这个距离是所有顶点中最大的。两个顶点u和v之间的距离是从u到v的路径上所有边的长度之和。

女孩们学习了园艺课程，所以她们知道如何修改树。Alice和Yuki可以花费c个硬币将树的根移动到当前根的一个邻接顶点上。这个操作可以执行任意次数（可能为零次）。注意，树的结构保持不变；唯一的变化是哪个顶点作为根。

朋友们想要出售能获得最大利润的树。利润定义为树的成本减去操作的总成本。

帮助女孩们找到通过应用任意次数（可能为零次）操作后能获得的最大利润。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含三个整数n、k、c（2≤n≤2×10^5；1≤k、c≤10^9），分别表示树中顶点的数量、每条边的长度和操作的成本。
- 接下来的n-1行，每行包含一对整数ui、vi（1≤ui、vi≤n），表示图中的边。这些边构成了一棵树。
- 所有测试用例的n值之和不超过2×10^5。

输出：
- 对于每个测试用例，输出一个整数，表示Alice和Yuki能获得的最大利润。

示例：
输入：
```
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
```
输出：
```
2
12
17
32
```题目大意： Alice和Yuki在他们的花园里种了一棵有n个顶点的树，树是一个没有环、自环或多条边的无向图。树中的每条边都有长度k。最初，顶点1是树的根。 Alice和Yuki种植这棵树不仅仅是为了好玩，她们还想要出售它。树的成本定义为从根到一个顶点的最大距离，这个距离是所有顶点中最大的。两个顶点u和v之间的距离是从u到v的路径上所有边的长度之和。 女孩们学习了园艺课程，所以她们知道如何修改树。Alice和Yuki可以花费c个硬币将树的根移动到当前根的一个邻接顶点上。这个操作可以执行任意次数（可能为零次）。注意，树的结构保持不变；唯一的变化是哪个顶点作为根。 朋友们想要出售能获得最大利润的树。利润定义为树的成本减去操作的总成本。 帮助女孩们找到通过应用任意次数（可能为零次）操作后能获得的最大利润。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含三个整数n、k、c（2≤n≤2×10^5；1≤k、c≤10^9），分别表示树中顶点的数量、每条边的长度和操作的成本。 - 接下来的n-1行，每行包含一对整数ui、vi（1≤ui、vi≤n），表示图中的边。这些边构成了一棵树。 - 所有测试用例的n值之和不超过2×10^5。 输出： - 对于每个测试用例，输出一个整数，表示Alice和Yuki能获得的最大利润。 示例： 输入： ``` 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 ``` 输出： ``` 2 12 17 32 ```