#P6874. 通商宽农
通商宽农
题目描述
给定一棵有 个结点的无向树。每条边的长度从实数区间 均匀随机抽取,各边独立。树上两点的距离为它们之间唯一简单路径的边长之和。对每次抽取,先求整棵树中两点之间的最大距离,再对这个最大值取期望。
输入格式
第一行一个整数 。接下来 行,每行两个整数 ,表示一条无向边。点从 到 编号。
输出格式
输出一行一个整数,表示期望对 取模。若期望为最简分数 ,输出与 同余的最小非负整数。
样例
5
1 2
2 3
3 4
4 5
2
数据范围
。
| 子任务 | 分值 | 附加条件 |
|---|---|---|
| 1 | 树是一条链 | |
| 2 | 19 | 至多一个点的度数不小于 2 |
| 3 | 30 | 至多一个点的度数不小于 3 |
| 4 | 50 | 无 |
By 郑钧天。原题面 PDF