挺巧妙的题，来理一下思路。
令 $m = \lceil \frac{n}{2} \rceil$。
考虑节点 $u$ 是树的重心的一种判定方法：$u$ 子树大小 $\geq m$，而其他子树大小都 $\lt m$。
设 $f_u$ 表示 $sz_u \geq m$ 的方案数，$g_u$ 表示 $u$ 是重心的方案数。
$f$ 是好求的，考虑枚举 $j=sz_i$：
$$f_i = \sum\limits_{j=m}^{n-i+1} \binom{n-i}{j-1} \times (j-1)! \times (n-j-1)! \times (i-1)$$
四项分别表示：
- $\binom{n-i}{j-1}$ 表示 $n-i$ 个点选择 $j-1$ 个把他们放在 $i$ 子树内。
- $(j-1)!$ 表示选中的点有多少种放置方法。设这个点是第 $p$ 个被放入的，那么它可以选择连接到之前放入的以及 $i$ 这些点共 $(j-1)-p+1+1=j-p+1$ 个点中，根据乘法原理总共有 $(j-1)!$ 种方法。
- $(n-j-1)!$ 和前者同理，只不过是在子树外排列。
- $(i-1)$ 表示从 $[1,i)$ 中选择一个点作为 $i$ 的父亲，方案数为 $i-1$。
这个东西看上去就很抽象，所以试着化简一下看看会变成什么：
$$f_i = \sum\limits_{j=m}^{n-i+1} \binom{n-i}{j-1} \times (j-1)! \times (n-j-1)! \times (i-1)$$
展开组合数，提出与 $i$ 相关项：
$$f_i = (n-i)! \times (i-1) \times \sum\limits_{j=m}^{n-i+1} \frac{(n-j-1)!}{(n-i-j-1)!}$$
右边是一个阶乘除以阶乘的形式，考虑把它补全成一个组合数，即除以 $(i-2)!$
$$f_i = (n-i)! \times (i-1) \times (i-2)! \times \sum\limits_{j=m}^{n-i+1} \frac{(n-j-1)!}{(n-i-j-1)!(i-2)!}$$
$$f_i = (n-i)! \times (i-1)! \times \sum\limits_{j=m}^{n-i+1} \binom{n-j-1}{i-2}$$
发现右边成了一个组合数求和的形式。
引理：$\sum\limits_{i=m}^{n} \binom{i}{m} = \binom{n+1}{m+1}$。
证明较为简单，大致就是手画一个杨辉三角，发现等号左边是一个竖着的长条求和，等号右边是长条最下面点的右下方。
根据组合数递推公式显然该引理成立。
于是原式化为：
$$f_i = (n-i)! \times (i-1)! \times \binom{n-m}{i-1}$$
$$\frac{f_i = (n-i)! \times (n-m)!}{(n-m-i+1)!}$$
现在可以 $O(1)$ 地求出 $f_i$ 了！
然后考虑如何求 $g_i$，$i$ 是重心当且仅当 $sz_i \geq m$ 且子树内不存在重心。
那么 $g_i = f_i - \frac{\sum\limits_{j=i+1}^n g_j}{i}$，即子树内仅存在 $j$ 这一个重心的方案数乘上 $j$ 在 $i$ 子树的概率。
为什么概率是 $\frac{1}{i}$？$j$ 不断往上跳，显然因为最后到达 $[1,i]$ 中每个点的概率是相等的。
于是我们只要倒着求 $g$ 数组并维护后缀和即可。
