Gardening Friends

#### 题意翻译 有一棵有 $n$ 个节点的树，根节点为节点 $1$，每条边的权值为 $k$。现在可以进行挪根操作，每次耗费 $c$ 价值，将树的根转移到与原来根结点相邻的点上。 定义这棵树的价值为根节点到子节点的最远距离 $a$ 与挪根耗费总价值 $b$ 之差（可能不会挪根）。求这棵树经过挪根操作后的最大价值 #### 输入格式 第一行一个正整数 $t$（$1\le t\le10^4$）为数据组数。 每组数据的第一行包括整数 $n$，$k$，$c$（$2\le n\le2\cdot10^5$，$1\le k,c\le10^9$），分别为节点数、边权和操作耗费价值。 接下来 $n-1$ 行每行描述一条边，节点为 $u_i,v_i$（$ 1\le u_i,v_i\le n$）。 #### 输出格式 一行一个正整数表示最大价值。

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).

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 $ .

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

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