Gardening Friends
Contest: Codeforces Round 867 (Div. 3)
Difficulty rating: 1700
Tags: brute force, dfs and similar, dp, graphs, trees

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 format:
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 format:
For each test case, output a single integer — the maximum profit that Yuki and Alisa can get.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
2
12
17
32

Editorial:
Let's first calculate its depth for each vertex. Let for a vertex $$$v$$$ its depth is $$$depth[v]$$$. All the values of $$$depth[v]$$$ can be calculated by a single depth-first search.
We introduce several auxiliary quantities. Let for vertex $$$v$$$ the values $$$down_1[v], down_2[v]$$$ are the two largest distances to the leaves in the subtree of vertex $$$v$$$ of the source tree. We will also introduce the value $$$up[v]$$$ - the maximum distance to the leaf outside the subtree of the vertex $$$v$$$.
The values of $$$down_1[v]$$$ and $$$down_2[v]$$$ are easily recalculated by walking up the tree from the bottom and maintaining two maximum distances to the leaves.
Let $$$p$$$ be the ancestor of the vertex $$$v$$$. Then to recalculate $$$up[v]$$$, you need to go up to $$$p$$$ and find the maximum distance to a leaf outside the subtree $$$v$$$. If the leaf farthest from $$$p$$$ is in the subtree $$$v$$$, then you will need to take $$$down_2[p]$$$, otherwise $$$down_1[p]$$$.
For $$$v$$$, we define the maximum distance to the leaf, as $$$dist[v] = max(down_1[v], up[v])$$$.
Now let's calculate for each vertex $$$v$$$ the cost of the tree if $$$v$$$ becomes the root. It is not profitable for us to take extra steps, so the cost of operations will be equal to $$$c\cdot depth[v]$$$. Then the cost of the tree will be equal to the value of $$$k\cdot dist[v] - c\cdot depth[v]$$$.
It remains to go through all the vertices, take the maximum of the tree values and get an answer. It is easy to see that such a solution works for $$$O(n)$$$.