OpenJudge

06:Power Station

总时间限制:
1000ms
内存限制:
65536kB
描述

The massive tsunami that struck the coastal city has washed away many of inhabitants andfacilities there. After the tsunami, the power supply facilities of the coastalcity are completely destroyed. People are in panic in the dark night. Doubtsremain over whether the communities will be able to rebuild the city. To calm people down, the heads of the city are planning to rebuild the city to startwith the recovery of the power supply facilities.

The coastal city consists of n communities which arenumbered from 1 to n. To save the electric cables, n-1cables has been used to connect these communities together, sothat each pair of communities is able to transfer electronic energy mutually.

The heads of the city decide to set a power station in one of the communities. There is thermal energy loss along the cables. Each cable has a resistance of Rohm. The total thermal energy loss isthe sum of I2Ri .Here Ri is the total residence along the path between the ithcommunity and the power station, and I is a constant. They are troubling their head on the issue of whereto set the power station to make the total thermal energy loss minimized.

输入
There are multiple test cases.
The first line contains one integer indicating the number of test cases.
For each test case, the first line contains three positive integers n, I and R, indicating the number of communities, the above mentioned constant and the residence of each cable. (3 ≤ n ≤ 50000, 1 ≤ I ≤ 10, 1 ≤ R ≤ 50)
The next n-1 lines, each describe a cable connection by two integers X, Y, which indicates that between community X and community Y, there is a cable.
输出
For each test case, please output two lines.
The first line is the minimum total thermal energy loss.
The second line is all the optional communities in ascending order.
You are requested to leave a blank line after each test case.
样例输入
2
5 1 1
3 2
1 2
5 2
4 3
6 1 2
1 2
2 3
3 4
2 6
3 5
样例输出
5
2

14
2 3

01,02 上学期数论问题。
03 BFS/DFS搜索。
04 最短路径问题
05 结合上周最小生成树和最短路径的思想:贪心

全局题号
5134
提交次数
9
尝试人数
4
通过人数
3