洛谷 4492 [HAOI2018] 苹果树 题解

洛谷 4492 [HAOI2018] 苹果树 题解

博客观赏效果更佳：
github
cnblogs

先膜一发 shadowice1984的题解，太神了！

题意简述

你有一个 n n n，表示你的二叉树将要有 n n n 个节点。然后每次你的树会等概率选择某个点的还没长过的儿子，在这里长一个儿子。容易证明，这样有 n ! n! n! 种方案。

（第一次有一种方案，第二次两种，第三次三种…一共就是 n ! n! n! 种）

然后你要输出树上路径和的期望值乘以 n ! n! n! 后   m o d   p bmod{p} modp 的值。

n , p n,p n,p 给定，满足： n ≤ 2000 , p ≤ 1 0 9 + 7 nle 2000,ple 10^9+7 n≤2000,p≤109+7

思路

考虑每条边的贡献：如果树是确定的，那么从 i i i 连向 i i i 父亲的边，的贡献是 s i z e i ( n − s i z e i ) size_i(n-size_i) sizei​(n−sizei​)。其中 s i z e u size_u sizeu​ 表示 u u u 的子树大小。枚举 i i i，把这个式子加起来就是答案了。

然后我们现在树是不确定的…注意到 n ≤ 2000 nle 2000 n≤2000，所以我们考虑再加一维枚举 s i z