当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6810:Imperative Meeting

题目描述
Some rumors about Zhang3 have been spread on the Internet. Zhang3 needs to dispel the rumors, but she's busy preparing her birthday party, so she asks her $m$ classmates for help. Her classmates decide to have a meeting for discussion.

The $m$ classmates live in the same community. There are $n$ houses in the community, labeled $1, 2, \ldots, n$. There are $(n - 1)$ roads connecting the houses, the $i^\mathrm{th}$ of which connects house $(i + 1)$ and $f_{i + 1}$, forming a tree. Each road is 1 km long.

The $m$ classmates live in $m$ different houses. They always choose such a house to have the meeting, that the total distance to travel for the $m$ classmates is minimized. The optimal total distance (in km) to travel is called the cost of the meeting.

Zhang3 doesn't know which houses her classmates live in, so there are $\binom{n}{m}$ different cases of that. Zhang3 wants to know the sum of the cost in all cases. As the answer can be very large, please help her calculate the answer modulo $10^9 + 7$.
输入解释
The first line of the input gives the number of test cases, $T \; (1 \le T \le 1000)$. $T$ test cases follow.

For each test case, the first line contains two integers $n, m \; (1 \le n \le 10^6, \; 1 \le m \le n)$, the number of houses in the community and the number of classmates.

The second line contains $(n - 1)$ integers $f_2, \ldots, f_n \; (1 \le f_i < i)$, separated by spaces, describing the roads.

The sum of $n$ in all test cases doesn't exceed $2 \times 10^6$.
输出解释
For each test case, print a line with an integer, representing the answer modulo $10^9 + 7$.
输入样例
2
4 3
1 1 1
5 3
1 2 3 3
输出样例
9
27
来自杭电HDUOJ的附加信息
Recommend liuyiding

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6810

最后修改于 2020-10-25T23:34:35+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
4000/2000MS(Java/Others) 524288/524288K(Java/Others)