题解：AT_abc290_f [ABC290F] Maximum Diameter
Iruka_Okazaki
·
2024-07-17 16:01:08
·
题解
神仙题目。
我们只需要考虑 \sum a_i = 2n - 2 并且 a_i > 0 的序列即可。
先考虑最大化树的直径，假如说 a 中有 k 个 1 ，即最后的树上一共有 k 个儿子节点，那么我们只需要把剩下的 n - k 个点排成一条链，然后再向两端加上两个叶子节点，剩余的叶子节点补到链上度数不够的节点。这样子直径的长度就是 n - k + 1 。然后我们考虑怎么计数。枚举 k ，那么叶子节点的选择方案数显然为 \dbinom nk 。如此一来剩下的节点的度数和就是 2n - 2 - k ，剩下的节点数就是 n - k 。那么就相当于把 2n - 2 - k 个球放到 n - k 个盒子里面，并且每一个盒子至少有 1 个球。那么其数量就为：
\dbinom {(2n - 2 - k) - 2(n - k) + (n - k) - 1}{(2n - 2 - k) - 2(n - k)} = \dbinom {n - 3}{k - 2}
那么在乘上链的长度，最终的答案就是 \sum^n_{i = 1}\dbinom nk \dbinom {n - 3}{k - 2} (n - k + 1) ，但是这个东西求一次要 O(n) 的复杂度，难以接受。
在继续化简的前面，我们需要了解两个式子：
上面两个都很好证明，在这里就不给证明了。然后就可以对于上面的式子进行化简了。
\begin{array}{l}
\sum^n_{k = 1} \dbinom nk \dbinom {n-2}{k-2} (n - k + 1)\\=
-\sum^n_{k = 1} \dbinom nk \dbinom {n-2}{k-2} (k - 2 + 1 - n)\\=
-\sum^n_{k = 1} \dbinom nk \dbinom {n-2}{k-2} (k - 2) + (n - 1) \sum^n_{k = 1} \dbinom nk \dbinom {n-2}{k-2}\\=
(n - 1) \sum^n_{k = 1} \dbinom nk \dbinom {n-2}{k-2} -(n - 3) \sum^n_{k = 1} \dbinom nk \dbinom {n-4}{k-3}\\=
(n - 1) \sum^n_{k = 1} \dbinom nk \dbinom {n-3}{n - k - 1} -(n - 3) \sum^n_{k = 1} \dbinom nk \dbinom {n-4}{n-k-1}\\=
(n - 1) \dbinom {2n-3}{n-1} - (n-3)\dbinom {2n-4}{n-3}
\end{array}
然后这样子就可以 O(1) 求出答案了。