题目描述

光头强在花园里种了一棵有 $n$ 个顶点的树。一棵树是一个无向图，没有环、自环或多重边。这棵树中的每条边都有长度 $k$。最初，顶点 $1$ 是树的根。

光头强种树不仅是为了好玩，他还想把它卖掉。这棵树的价值定义为根节点到树中所有顶点的最大距离。两个顶点 $u$ 和 $v$ 之间的距离是从 $u$ 到 $v$ 路径上所有边的长度之和。

光头强学过园艺课程，所以知道如何修改树。他可以花费 $c$ 枚硬币将树的根移动到其相邻节点。此操作可以执行任意次数（可能为零）。请注意，树的结构保持不变；唯一的变化是根节点的编号。

光头强想以最大的利润出售树。利润定义为树的价值减去操作的总成本。

帮助光头强找到通过对树进行任意次数的操作（可能为零）可以获得的最大利润。

输入格式

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

接下来的每个测试用例的第一行包含整数 $n,k,c(2≤n≤2⋅10^5;1≤k,c≤10^9)$- 树中顶点的数量，每条边的长度和操作的成本。

测试用例的下一个 $n-1$ 行包含 $u_i,v_i(1≤u_i,v_i≤n)$- 图的边。这些边形成一棵树。

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

输出格式

对于每个测试用例，输出一个整数- 光头强可以获得的最大利润。

测试样例

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

样例说明

样例1：$1$ 为根，$23$ 为其儿子，初始利润为 $2$。如果改造，价值将变为 $4$，但是需要耗费 $3$ 的代价，利润为 $1$。

样例2：$1$ 为根，最深的节点深度为 $3$，利润为 $12$。修改后深度会变小。

样例3：$1$ 为根，有 $3$ 个儿子，分别为 $456$，初始深度为 $3$，对应利润为 $3×5=15$。可以将根移动到 $4$ 或者 $5$，这样深度变为 $4$，对应利润为 $4×5-3=17$。

样例4：$1$ 为根，有 $39$ 两个儿子。$9$ 路径比较复杂，有两条路径探底：$1→9→7→6→4$，$1→9→2→8→5→10$。最优方案为将根移动到 $3$，这样最大深度为 $6$，对应利润为 $6×6-4=32$。

如果你老是 WA，想想有什么漏洞？