题意
现在有 $n$ 次操作，每次从当前二叉树上的所有空位（节点的左/右儿子）中等概率选择一个，插入新点。
对最终 $n$ 个点的二叉树，求：两两节点距离之和的期望。
题解
加入第 $i$ 个点时，方案数为 $i$，根据乘法原理，一共有 $n!$ 种可能的二叉树。只需要计算这些树的权值和。
由于是统计距离之和，考虑按边拆开计算，一条边被经过的次数，能直接算，是这条边两侧的节点个数的乘积。
所以先枚举边。形式化地，枚举 $i\in[2, n]$，则当前边是 $\langle i,\operatorname{father}_i\rangle$，其被经过的次数为 $\operatorname{size}_{i}(n – \operatorname{size}_i)$.
由于 $\operatorname{size}_i$ 并不知道，所以再枚举子树大小 $\operatorname{size}_i\in[1, n-i+1]$.
接下来我们要确定树的形态，求满足 $\operatorname{size}_i$ 限制的方案数，按照插入的顺序分别考虑。
\underbrace{1\quad2\quad3\quad \cdots\quad i-2\quad i-1\quad i}_{A}\quad\underbrace{ i+1\quad i+2\quad \cdots\quad n-2\quad n-1\quad n}_{B}
$$
$A$ 段
包含前 $i$ 个点，这些点和 $i$ 的子树没什么关系，都可以随便插入，共有 $i!$ 种方案。
$B$ 段
我们首先要从中选出 $\operatorname{size}_i-1$ 个节点插入 $i$ 的子树，共有 $\dbinom{n-i}{\operatorname{size}_i-1}$ 种方案。
这 $\operatorname{size_i}$ 个点是可以以任意顺序组成二叉树的，共有 $(\operatorname{size}_i)!$ 种方案。
对于 $B$ 中剩下的 $n-i-\operatorname{size}_i+1$ 个点，它们都不可以放在 $i$ 的子树内，下面计算这部分的方案数。
上图中，$i=9$，可以发现此时共有 $8=i-1$ 个位置可供选择。
并且，每当我们插入一个节点，可供选择的位置就会增加 $1$。
所以把 $B$ 中剩下的点插入的方案数为：$(i-1)i(i+1)\cdots(n-\operatorname{size}_i-1)=\dfrac{(n-\operatorname{size}_i-1)!}{(i-2)!}$.
把上面的方案数都乘起来，再乘上 $\langle i,\operatorname{father}_i\rangle$ 这条边的贡献，得到答案的表达式：
\operatorname{Ans} = \sum_{i=2}^{n}\sum_{\operatorname{size}_i=1}^{n-i+1} \operatorname{size}_i(n – \operatorname{size}_i) \cdot i!\cdot \binom{n-i}{\operatorname{size}_i-1}(\operatorname{size}_i)! \cdot \frac{(n-\operatorname{size}_i-1)!}{(i-2)!}
$$
把 $i!$ 与 $(i-2)!$ 合并，得到：
\operatorname{Ans} = \sum_{i=2}^{n}\sum_{\operatorname{size}_i=1}^{n-i+1} \operatorname{size}_i(n – \operatorname{size}_i) \cdot \binom{n-i}{\operatorname{size}_i-1}(\operatorname{size}_i)! \cdot {(n-\operatorname{size}_i-1)!}\cdot i(i-1)
$$
预处理阶乘和组合数，$\mathcal{O}(n^2)$ 计算即可。
代码
为了提高可读性，下面代码中统计答案部分的取模操作被省去，直接提交将获得 $\rm{20pts}$ 的好成绩。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e3 + 10;
int N, P;
int fac[MAXN], C[MAXN][MAXN], ans;
signed main() {
cin >> N >> P;
fac[0] = 1;
for(int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % P;
for(int i = 0; i <= N; i++) C[i][0] = 1;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= i; j++)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % P;
for(int i = 2; i <= N; i++) {
for(int siz = 1; siz <= N - i + 1; siz++) {
ans += C[N - i][siz - 1] * siz * (N - siz) * fac[siz] * fac[N - siz - 1] * i * (i - 1);
}
}
cout << ans << endl;
return 0;
}