园艺好友

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

Alisa 和 Yuki 在花园里种了一棵有 $n$ 个顶点的树。树是一张无环、无自环且无重边的无向连通图。树中每条边的长度都为 $k$，初始时顶点 $1$ 是树根。

一棵树的售价定义为：树根到所有顶点距离的最大值。两点间的距离是它们之间唯一路径上各边长度之和。

你可以花费 $c$ 枚硬币，把当前树根移动到它的一个相邻顶点。该操作可以执行任意次，也可以一次都不执行；树的结构始终不变。

最终收益等于树的售价减去所有移动操作的总花费。求能够得到的最大收益。

输入格式

第一行包含一个整数 $t$（$1\le t\le10^4$），表示测试用例数。

每个测试用例的第一行包含三个整数 $n,k,c$（$2\le n\le2\times10^5$，$1\le k,c\le10^9$），分别表示顶点数、每条边的长度和一次移动的费用。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示树的一条边。输入保证这些边构成一棵树。

所有测试用例的 $n$ 之和不超过 $2\times10^5$。

输出格式

对每个测试用例输出一行最大收益。

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

数据范围