园艺之友（garden）

题目描述

Y 同学拥有一棵包含 $n$ 个节点的树，初始时该树的根节点为 $1$。树中每一条边的权重均为 $k$。

Y 同学可以对这棵树进行若干次“挪根”操作。每次操作中，他可以将当前的根节点移动至与其相邻的一个节点上。每执行一次挪根操作，均需要花费 $c$ 的代价。

定义一棵以 $u$ 为根节点的树的“美观度”为：

1. 令 $D(u)$ 表示在当前的树结构中，根节点 $u$ 到树中所有节点距离的最大值。
2. 令 $W(u)$ 表示将根节点从初始位置 $1$ 移动至当前位置 $u$ 所花费的总代价。
3. 该树的美观度定义为 $D(u) - W(u)$。

请你帮助 Y 同学计算，通过若干次（也可以不进行）挪根操作后，这棵树所能达到的最大美观度。

输入格式

第一行包含一个整数 $T$，表示数据组数。

对于每组数据： 第一行包含三个整数 $n, k, c$，分别表示节点的数量、每条边的权重以及单次移动根节点的代价。 接下来 $n-1$ 行，每行包含两个整数 $u_i, v_i$，表示节点 $u_i$ 与 $v_i$ 之间存在一条无向边。

输出格式

对于每组数据，输出一行一个整数，表示该树所能达到的最大美观度。

样例

样例输入 #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

数据范围与约定

对于 $100\%$ 的数据，满足 $1 \le T \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$1 \le k, c \le 10^9$。 保证所有测试点中 $n$ 的总和不超过 $2 \cdot 10^5$。

• 特殊性质 A：保证 $c \ge n \cdot k$。
• 特殊性质 B：保证输入的树是一条链。