Рабочее место участника

Your country consists of a number of villages connected by roads. There are just enough roads to insure that all villages are mutually connected, directly or indirectly, but not one road more. When the enemies invade, they will always land on a road, halfway between two villages, and spread out from there. To defend the roads, you can place guard robots in the villages. There are two types: soldier-bots and sergeant-bots. A soldier-bot, when placed in a village, protects all roads connected to that village. A sergeant-bot is more powerful: it protects the roads connected to the village it is placed in, but also all roads connected to the villages that are direct neighbors to it. Both types of robot come at a price, and it's your task to assign robots to villages such that: a) all roads are protected, b) the total cost of the robots is as low as possible.

Input starts with three numbers on a line by itself: `N` (`1\ ≤\ N\ ≤\ 10000`), the number of villages, `C_1` (`0\ ≤\ C_1\ ≤\ 1000`), the cost of a soldier-bot, and `C_2` (`0\ ≤\ C2\ ≤\ 1000`), the cost of a sergeant-bot. For the sake of abstraction, the villages are numbered from 1 to `N`. Then follow `N-1` lines containing two numbers `V_1` (`1\ ≤\ V_1\ ≤\ N`) and `V_2` (`1\ ≤\ V_2\ ≤\ N`), each defining a road between two villages, numbered `V_1` and `V_2`, respectively. No road is mentioned twice, and all roads together span all villages.

Print just one number: the minimal cost of protecting country.

5 30 50
1 2
2 3
3 4
4 5

50

9 20 30
1 2
2 3
3 4
4 5
4 8
5 6
5 7
8 9

50

6 100 500
1 3
2 3
3 4
4 5
4 6

200