#P7205. [2018西部多校]Expectation
[2018西部多校]Expectation
题目描述
给定一棵 个结点的树。每条边的长度独立地从区间 均匀选取。长度确定后,求两个不同结点之间的最大距离,即这棵带权树的直径。
求直径长度的期望,对 取模。若期望写作既约分数 ,输出 。
输入格式
第一行一个整数 。接下来 行,每行两个整数 ,表示树的一条边。结点编号为 。
输出格式
一行一个整数,表示答案。
样例
5
4 2
2 3
3 1
3 5
382660337
数据范围与约定
对所有数据,。
| 测试点 | 的上界 | 附加性质 |
|---|---|---|
| 1–2 | ||
| 3–6 | 每条边满足 | |
| 7–10 | 每条边满足 | |
| 11–14 | ||
| 15–18 | ||
| 19–20 |