print973. Protecting country

printRoads

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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
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.
Output
Print just one number: the minimal cost of protecting country.

Sample Input 1

5 30 50
1 2
2 3
3 4
4 5

Sample Output 1

50

Sample Input 2

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

Sample Output 2

50

Sample Input 3

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

Sample Output 3

200
Source: Весенний турнир имени Мартовского зайца, 2007, ICPC Dhaka Asia RC, 2006
loading