4932: Hamiltonian Spanning Tree
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：1
通过：1
题目描述
D. Hamiltonian Spanning Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
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 desc
Input
The first line of the input contains three integers n, x and y (2≤n≤200000,1≤x,y≤109). Each of the next n-1 lines contains a desc
Output
Print a single integer− the minimum number of seconds one needs to spend in order to visit all the cities exactly once.
Examples
Input
5 2 3 1 2 1 3 3 4 5 3
Output
9
Input
5 3 2 1 2 1 3 3 4 5 3
Output
8
Note
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
. 输入样例 复制
输出样例 复制