Logo 邂逅编程之美

UOJ

时间限制:2 s 空间限制:512 MB
Statistics

【题目描述】

在一棵树上,每个点有一个人。

现在,白兔想召开一个聚会。如果在聚会上,白兔见到了 $k$ 个人,则它会获得 $w\times\sqrt{k}$ 的快乐值。

但是,其他人不想去太远的地方参加聚会。如果白兔选择在点 举办聚会,位于点 的人来参加聚会,则会有一个不满意值,为 $i$ 和 $j$ 的距离。

现在,你需要帮助白兔想一想,让哪些人到哪个地方来参加聚会,可以使得白兔的快乐值减去其他人的 不满意值最大。

【输入格式】

第一行两个正整数 $n,w$。 接下来 $n-1$ 行,每行两个数表示一条树边。

【输出格式】

输出最大值。保留两位小数。

【输入样例1】

5 2
1 2
1 3
1 4
4 5

【输出样例1】

2.00

【样例解释】

随便选择在一个点 $x$ 开聚会,然后就只让 $x$ 一个人来参加。

【输入样例2/3/4】

见下发文件

【输出样例2/3/4】

见下发文件

【数据范围与约定】

对于 10% 的数据,$w=1$

对于 30 %的数据,$n\le100$

对于 50% 的数据,$n\le3000$

对于 100% 的数据,$1\le n\le2\times10^5,1\le w\le10^9$

下发文件