#P18534. Expected Diameter

Expected Diameter

Expected Diameter

如果你有为竞赛准备题目的经历,下面这个事实可能显得反直觉:从所有有 nn 个节点的无根带标号树中均匀随机选一棵,它的期望直径是 Θ(n)\Theta(\sqrt n)。

为什么这很反直觉呢?如果你准备过树上的题目,可能知道一种很简单的随机树生成方式(但它不保证均匀),这里称为“偏斜随机生成器”:

  • 对每个 i=2,3,…,ni=2,3,\ldots,n,均匀随机选择一个 1≤j<i1\le j<i,加入边 (i,j)(i,j)。
  • 最后,随机选择 1,2,…,n1,2,\ldots,n 的一个排列,用它重新标号所有节点。

这当然并非从全部 nn−2n^{n-2} 棵无根带标号树中均匀选择——nn−2n^{n-2} 来自 Cayley 公式。但直觉上,你可能认为这个分布已经“足够接近”均匀,应该能给出正确的期望直径。用这个过程生成的树,其期望直径为 Θ(log⁡n)\Theta(\log n)(原作者附注:至少他认为如此)。然而,这个直觉并不正确:偏斜生成器在 nn−2n^{n-2} 棵树上产生的分布偏差,足以改变期望直径。

现在用下面这个随机过程来检验这一认识。随机生成一棵有 nn 个节点的带权无根带标号树:

  1. 首先,在全部 nn−2n^{n-2} 棵无权无根带标号树中,均匀随机选一棵。特别强调:不使用上面背景介绍的偏斜生成器。
  2. 然后,对每条边独立赋权:以概率 p1p_1 赋权 11,以概率 p2p_2 赋权 22,其中 p1+p2=1p_1+p_2=1。

给定 nn,求这样选出的树的期望直径,并将结果“模 998244353998244353”输出。具体地:

  • 令 m=998244353m=998244353。
  • 当 p1,p2p_1,p_2 为有理数时,答案也是有理数。
  • 将答案约分成 u/vu/v,其中 v>0v>0。
  • 在本题的约束下,存在唯一整数 rr 满足 0≤r<m0\le r<m 且 rv≡u(modm)rv\equiv u\pmod m。你需要输出这个 rr。

定义:

  • 有 nn 个节点的无根带标号树,是顶点恰为 1,2,…,n1,2,\ldots,n 的连通、无环、无向图。
  • 带权图的直径,是其中所有简单路径的最大权值。
  • 简单路径是一列互不相同的节点 s0,s1,…,sks_0,s_1,\ldots,s_k,相邻节点之间都有边。
  • 路径的权值,是它经过的全部边权之和。单节点树的直径为 00。

输入格式

输入只有一行,包含三个整数 n,x,yn,x,y。概率定义为

p1=xy,p2=1−p1.p_1=\frac{x}{y},\qquad p_2=1-p_1.

约束为 1≤n≤20001\le n\le2000,0≤x≤y≤10000\le x\le y\le1000,并且上述分式有定义,即 1≤y≤10001\le y\le1000。

概率范围说明: p1=x/yp_1=x/y 是有定义的有理概率,因此除 0≤x≤y≤10000\le x\le y\le1000 外,还须满足 y≥1y\ge1;0/00/0 不定义为概率,也不指定相应答案。

输出格式

输出一行一个整数,表示所求期望直径模 998244353998244353 的结果,范围为 [0,998244353)[0,998244353)。

原样例 1

2 1 3
665496237

原样例 2

3 2 3
665496238

原样例说明

n=2n=2 时,只有 20=12^0=1 棵无权树,以及 22 种带权树。它们的直径分别为 11、22,对应概率为 1/31/3、2/32/3,期望直径为 5/35/3。答案 665496237665496237 是唯一满足 0≤r<9982443530\le r<998244353 及 3r≡5(mod998244353)3r\equiv5\pmod{998244353} 的整数。

n=3n=3 时,有 31=33^1=3 棵无权树,以及 1212 种带权树。