奖励：纯粹通过生成函数来解决问题。
le0n
·
·
个人记录
我们发现根的区间必须完全包含于子孙的区间或者与其不交，因此只考虑这颗子树内的相对大小时，根的区间形如 [i,i+1]。
因此一棵树的答案是 \frac{(2n)!}{2^{n}\prod s_i}。
直接生成函数，有 \frac{df}{dx}=e^f+(y-1)。
这里 y 表示叶子的个数，x 表示总结点数，我们要求的答案是 \frac{(2n)!n!}{n2^n}[x^ny^k]f。
为了方便起见，下面都用 f' 表示 \frac{df}{dx}。
f'=e^f+y-1\\
f'e^{-f}=1+(y-1)e^{-f}\\
设 g=e^{-f}，那么有
-g'=1+(y-1)g\\
-e^{(y-1)x}=e^{(y-1)x}g'+(y-1)e^{(y-1)x}g\\
设 h=e^{(y-1)x}g，那么有
-e^{(y-1)x}=h'\\
h=\frac{e^{(y-1)x}}{1-y}+C\\
这里 h 的常数项为 1，因此 C=-\frac{y}{1-y}
g=\frac{1}{1-y}-\frac{ye^{(1-y)x}}{1-y}\\
f=-\ln(\frac{1-ye^{(1-y)x}}{1-y})=\ln(1-y)-\ln(1-ye^{(1-y)x})
n![x^ny^k]f=\sum_{i=1}^k (-1)^{n-k+i}i^{n-1}\binom{n}{k-i}
然后就可以 O(n) 预处理 O(k\log_k n) 计算答案，或者 O(n\log n) 计算一行答案。
upd：好像也不需要 O(n) 预处理。