408528: GYM103181 I Starlight

You are given a tree and two possible operations that can be applied to the tree:

• First operation, with cost $$$c_1$$$: Pick a chain $$$x_1$$$ - $$$x_2$$$ - $$$x_3$$$ ($$$x_1$$$ connected to $$$x_2$$$, $$$x_2$$$ connected to $$$x_3$$$). For each of $$$x_3$$$'s neighbors (except for $$$x_2$$$), we remove their edges to $$$x_3$$$ and instead connect them to $$$x_1$$$. $$$x_3$$$ also removes it's edge to $$$x_2$$$ and connect it to $$$x_1$$$.
• Second operation, with cost $$$c_2$$$: Pick a chain $$$x_1$$$ - $$$x_2$$$ - $$$x_3$$$ ($$$x_1$$$ connected to $$$x_2$$$, $$$x_2$$$ connected to $$$x_3$$$). For each of $$$x_3$$$'s neighbors (except for $$$x_2$$$), we remove their edges to $$$x_3$$$ and instead connect them to $$$x_1$$$. Then, remove $$$x_3$$$ from the tree. (The same as the previous operation, but instead of connecting to $$$x_1$$$, node $$$x_3$$$ is completely removed from the tree)

Find the minimum cost necessary to transform the tree into a star.

A star is a special type of tree with $$$n$$$ nodes, in which $$$n - 1$$$ vertices have degree $$$1$$$ and a single vertex has degree $$$n - 1$$$ (is connected to all other vertices).

The first line of the input contains the number of nodes, $$$3 \le N \le 10^5$$$, and the costs of the two operations, $$$1 \le c_1, c_2 \le 10^9$$$.

The following $$$n - 1$$$ lines each contain two integers $$$a, b$$$, with $$$1 \le a, b \le n$$$, meaning that there is a bidirectional edge between node $$$a$$$ and node $$$b$$$.

The only line in the output should contain an integer representing the minimum cost necessary to transform the tree into a star.

5 10 15
1 2
2 3
3 4
4 5

10