Codeforces Round 867 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

dfs and similar

dp

graphs

trees

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Gardening Friends

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTwo 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

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

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

Example

Input

43 2 32 13 15 4 12 14 25 43 46 5 34 16 12 65 13 210 6 41 31 99 77 66 49 22 88 55 10

Output

2 12 17 32

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 19:43:39 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|