#P6874. 通商宽农

    ID: 6705 传统题 1000ms 888MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS树直径树形 DP概率 DP分段多项式普通多项式乘法分段解析积分期望线性性模逆元

通商宽农

题目描述

给定一棵有 nn 个结点的无向树。每条边的长度从实数区间 [0,1][0,1] 均匀随机抽取,各边独立。树上两点的距离为它们之间唯一简单路径的边长之和。对每次抽取,先求整棵树中两点之间的最大距离,再对这个最大值取期望。

输入格式

第一行一个整数 nn。接下来 n−1n-1 行,每行两个整数 u,vu,v,表示一条无向边。点从 11 到 nn 编号。

输出格式

输出一行一个整数,表示期望对 998244353998244353 取模。若期望为最简分数 a/ba/b,输出与 ab−1a b^{-1} 同余的最小非负整数。

样例

5
1 2
2 3
3 4
4 5
2

数据范围

1≤n≤1001\le n\le100。

子任务 分值 附加条件
1 树是一条链
2 19 至多一个点的度数不小于 2
3 30 至多一个点的度数不小于 3
4 50 无

By 郑钧天。原题面 PDF