#P7205. [2018西部多校]Expectation

    ID: 7021 传统题 2000ms 888MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS树直径贡献法概率 DP换根 DP前后缀合并排除子节点分段多项式普通多项式乘法导数积分转化模逆元

[2018西部多校]Expectation

题目描述

给定一棵 nn 个结点的树。每条边的长度独立地从区间 [0,1][0,1] 均匀选取。长度确定后,求两个不同结点之间的最大距离,即这棵带权树的直径。

求直径长度的期望,对 998244353998244353 取模。若期望写作既约分数 A/BA/B,输出 A⋅B−1 mod 998244353A\cdot B^{-1}\bmod 998244353。

输入格式

第一行一个整数 nn。接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i,表示树的一条边。结点编号为 1,…,n1,\ldots,n。

输出格式

一行一个整数,表示答案。

样例

5
4 2
2 3
3 1
3 5
382660337

数据范围与约定

对所有数据,3≤n≤1003\le n\le100。

测试点 nn 的上界 附加性质
1–2 55
3–6 100100 每条边满足 ui=vi−1u_i=v_i-1
7–10 每条边满足 ui=1u_i=1
11–14 1010
15–18 2020
19–20 100100

原 PDF 题面