Description
The massive tsunami that struck the coastal city has washed away many of
inhabitants and facilities there. After the tsunami, the power supply facilities of the
coastal city are completely destroyed. People are in panic in the dark night. Doubts
remain 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 start with the recovery
of the power supply facilities.
The coastal city consists of n communities which are numbered from 1 to n. To
save the electric cables, n-1 cables has been used to connect these communities
together, so that 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 R ohm.
The total thermal energy loss is the sum of I^2*
Ri . Here
Ri is the total residence along
the path between the
ith community and the power station, and I is a constant. They
are troubling their head on the issue of where to set the power station to make the total
thermal energy loss minimized.
Input
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.
Output
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.
Sample Input
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
樹形dp,求出樹上所有點到其他點的距離和
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=50005;
vector<int> tree[maxn];
LL x,y,T,n,cnt[maxn],sum[maxn],f[maxn];
LL I,R;
void dfs(int x,int fa)
{
cnt[x]=1; sum[x]=0;
for (int i=0;i<tree[x].size();i++)
if (tree[x][i]!=fa)
{
dfs(tree[x][i],x);
cnt[x]+=cnt[tree[x][i]];
sum[x]+=cnt[tree[x][i]]+sum[tree[x][i]];
}
}
void Dfs(int x,int fa)
{
for (int i=0;i<tree[x].size();i++)
if (tree[x][i]!=fa)
{
f[tree[x][i]]=f[x]-cnt[tree[x][i]]+n-cnt[tree[x][i]];
Dfs(tree[x][i],x);
}
}
int main()
{
scanf("%lld",&T);
while (T--)
{
scanf("%lld%lld%lld",&n,&I,&R);
for (int i=1;i<=n;i++)
{
tree[i].clear();
f[i]=cnt[i]=sum[i]=0;
}
for (int i=1;i<n;i++)
{
scanf("%lld%lld",&x,&y);
tree[x].push_back(y);
tree[y].push_back(x);
}
dfs(1,1);
f[1]=sum[1];
Dfs(1,1);
LL ans=0x7FFFFFFF;
for (int i=1;i<=n;i++) ans=min(ans,f[i]);
printf("%lld\n",ans*I*I*R);
int flag=0;
for (int i=1;i<=n;i++)
if (f[i]==ans)
{
if (flag) printf(" ");
else flag=1;
printf("%d",i);
}
printf("\n\n");
}
return 0;
}