In a star system far, far away, there are two civilised planets: Zonq and Clunq. Zonq is a lovely planet with plenty of natural resources and its inhabitants, the zonq-ians, developed into a peace-loving people, with high moral standards and a rich culture of arts, sciences and all things nice. Clunq, on the other hand, is a cold, dark planet where the resources are scarce, and its inhabitants, the clunq-ons, struggle for their existence from the day they are born. It is no wonder they developed into strong fighters, and martial arts are their main form of culture. As always happens in the universe, at some point in their development the clunq-ons in- vented space exploration, and now they are on the verge of loading their space-ships with warriors to conquer Zonq. Although the zonq- ians developed mathematics to a very high level (they factorize million digit numbers for break- fast and the proof of Fermat’s Last Theorem is taught in elementary school), they never bothered to tire themselves with such mundane things as computers and informatics. So now they need your help to defend the planet. Zonq consists of a number of villages con- nected by roads. Since the zonq-ians hate phys- ical labour, they built just enough roads to in- sure that all villages are mutually connected, directly or indirectly, but not one road more. When the clunq-ons invade, they will always land on a road, halfway between two villages, and spread out from there. To defend the roads, the zonq-ians can place guard robots in their 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 There are several scenarios. Each scenario starts with three numbers on a line by it self: N (1 ≤ N ≤ 10000), the number of villages, C1 (0 ≤ C1 ≤ 1000), the cost of a soldier-bot, and C2 (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 V1 (1 ≤ V1 ≤ N) and V2 (1 ≤ V2 ≤ N), each defining a road between two villages, numbered V1 and V2, respectively. No road is mentioned twice, and all roads together span all villages. A line with three zeros marks the end of the input and should not be processed. Output For each scenario in the input, print just one number on a line by it self: the minimal cost of protecting Zonq.
2/2 PS. How were the zonq-ians able to utilize robots, if they never bothered to build computers? Well, that’s a stupid question: they called 0800-RENT-A-BOT, of course! How else do you think they hired you, in the first place? Sample Input 5 30 50 12 23 34 45 9 20 30 12 23 34 45 48 56 57 89 6 100 500 13 23 34 45 46 000 Sample Output 50 50 200