吸收恒等式、范德蒙德卷积。
为什么我能切黄题的场我都没打啊 /ll
先考虑确定度数数组时怎么做。显然 \(\sum x_i = 2n-2\)。
手玩一下发现答案是 \(\sum [x_i > 1] + 1\)。
证明？\(x_i=1\) 就是叶子，考虑到最多两片叶子参与构造直径，就做完了。把其它点上下串起来，前后各放一片叶子，如果仍缺少度数则往下挂儿子。因为 \(\sum x_i=2n-2\)，点一定刚好用完。
枚举 \(\sum [x_i>1]\)，然后枚举具体分配方案，最后在总数中选出有值的数字。
设共 \(k\) 数，具体分配方案：预先每数减一 \(n-2\) 分为 \(k\) 份非零。
\[=\sum_{k=1}^{n-2} \binom{n-3}{k-1} \binom{n}{k} (k+1) \]它很范德蒙德卷积啊，但是有个 \(k+1\)，要把它吸收掉。
熟知的吸收恒等式：\(\displaystyle \binom{n}{k} = \dfrac{n}{k} \binom{n-1}{k-1}\)。化一下即 \(\displaystyle k\binom{n}{k} = n\binom{n-1}{k-1}\)。
\[=\sum_{k=1}^{n-2} n\binom{n-3}{k-1} \binom{n-1}{k-1} + \sum_{k=1}^{n-2} \binom{n-3}{k-1} \binom{n}{k} \]它的上指标是定值，下指标差也是定值，这不反转下指标做范德蒙德卷积：
\[= n \sum_{k=1}^{n-2} \binom{n-3}{k-1} \binom{n-1}{n-k} + \sum_{k=1}^{n-2} \binom{n-3}{k-1} \binom{n}{n-k} \]\[= n \binom{2n-4}{n-1} + \binom{2n-3}{n-1} \]\(\square\).
再给我一次机会，我绝对不会错过这场在周日的 abc。
标签：卷积,题解,sum,abc290F,binom,2n,德蒙 From： https://www.cnblogs.com/purplevine/p/17137663.html