没动脑子就 gf 一路写下来了......实际上就是把插板法的 gf 写了一下/zk
首先考虑一下一个 \(X\) 合法是什么情况，那就是总和是 \(2n-2\) 并且保证 \(0<X_i<n\)。
证明就考虑贪心构造一下，每个 \(1\) 挂在一个 \(\geq 2\) 的上面，不断挂使得最后只剩下两个 \(1\) 和一堆 \(2\)，再把它们串起来就行。
然后就能发现，这样也同时构造出了最大的直径（容易发现这是上界），那就是 度数 \(\geq 2\) 的个数 + 1．
然后枚举度数为 1 的有 \(k\) 个，此时答案为 \(n-k+1\)，先仅考虑度数 \(\geq 2\) 内部的顺序，最后乘上 \(\binom{n}{k}\) 以插入度数为 1 的。这样要算的方案数就是：
\[\begin{aligned} &[z^{2n-2-k}](z^2+z^3+\cdots+z^{n-1})^{n-k} \\ =&[z^{2n-2-k-2(n-k)}](1+z+z^2+\cdots+z^{n-3})^{n-k} \\ =&[z^{k-2}](1+z+z^2+\cdots+z^{n-3})^{n-k} \end{aligned} \]由于 \(k\leq n-1\)，那么 \(n-3\geq k-2\)，所以：
\[\begin{aligned} =&[z^{k-2}](1+z+z^2+z^3+\cdots)^{n-k} \\ =&[z^{k-2}]\left(\frac{1}{1-z}\right)^{n-k} \end{aligned} \]已经化到我们熟悉的形式了，根据广义二项式定理它的系数就是 \(\binom{n-k+k-2-1}{k-2}=\binom{n-3}{k-2}\)，最后答案的推导也是平凡的。
\[\begin{aligned} &\sum_{k=2}^{n-1}\binom{n}{k}\binom{n-3}{k-2}(n-k+1) \\ =&(n-1)\sum_{k=2}^{n-1}\binom{n}{k}\binom{n-3}{k-2}-\sum_{k=2}^{n-1}\binom{n}{k}\binom{n-3}{k-2}(k-2) \\ =&(n-1)\sum_{k=2}^{n-1}\binom{n}{n-k}\binom{n-3}{k-2}-(n-3)\sum_{k=3}^{n-1}\binom{n}{n-k}\binom{n-4}{k-3} \\ =&(n-1)\binom{2n-3}{n-2}-(n-3)\binom{2n-4}{n-3} \end{aligned} \]倒数第二步同时用了对称恒等式和吸收恒等式，最后一步则是范德蒙德卷积。
Code：https://atcoder.jp/contests/abc290/submissions/39046485
标签：geq,题解,sum,Maximum,cdots,ABC290F,binom,aligned,2n From： https://www.cnblogs.com/do-while-true/p/17261642.html