CF618D.Hamiltonian Spanning Tree

A group of n cities is connected by a network of roads. There is an undirected road between every pair of cities, so there are roads in total. It takes exactly y seconds to traverse any single road.

A spanning tree is a set of roads containing exactly n - 1 roads such that it's possible to travel between any two cities using only these roads.

Some spanning tree of the initial network was chosen. For every road in this tree the time one needs to traverse this road was changed from y to x seconds. Note that it's not guaranteed that x is smaller than y.

You would like to travel through all the cities using the shortest path possible. Given n, x, y and a description of the spanning tree that was chosen, find the cost of the shortest path that starts in any city, ends in any city and visits all cities exactly once.

有 $n$ 座城市，由一张道路网络连接。每对城市之间都有一条无向道路，因此总共有 条道路。经过任意一条道路恰好需要 $y$ 秒。

一棵生成树是指包含恰好 $n-1$ 条道路的子集，且仅使用这些道路即可在任意两座城市之间通行。

初始网络的某棵生成树被选定。对于该生成树中的每条道路，其通行时间由 $y$ 秒改为 $x$ 秒。注意：不能保证 $x < y$。

你希望以最短的总时间遍历所有城市（即访问每座城市恰好一次）。给定 $n$、$x$、$y$ 以及所选生成树的描述，请计算从任意城市出发、在任意城市结束、且恰好访问所有城市一次的最短路径的总代价。

The first line of the input contains three integers n, x and y (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 109).

Each of the next n - 1 lines contains a description of a road in the spanning tree. The i-th of these lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n) — indices of the cities connected by the i-th road. It is guaranteed that these roads form a spanning tree.

输入的第一行包含三个整数 $n$、$x$ 和 $y$（$2 \leq n \leq 200\,000$，$1 \leq x, y \leq 10^9$）。

接下来的 $n-1$ 行每行描述生成树中的一条道路。其中第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示第 $i$ 条道路所连接的两个城市的编号。保证这些道路构成一棵生成树。

Print a single integer — the minimum number of seconds one needs to spend in order to visit all the cities exactly once.

输出一个整数——即恰好访问所有城市一次所需的最少秒数。

In the first sample, roads of the spanning tree have cost 2, while other roads have cost 3. One example of an optimal path is .

In the second sample, we have the same spanning tree, but roads in the spanning tree cost 3, while other roads cost 2. One example of an optimal path is .

在第一个样例中，生成树中的道路代价为 2，而其他道路的代价为 3。一个最优路径示例如下：。

在第二个样例中，生成树相同，但生成树中的道路代价为 3，而其他道路的代价为 2。一个最优路径示例如下：。