当前位置：首页 > news >正文

【未完工题解】AT_abc290_f [ABC290F] Maximum Diameter

news 2026/7/4 16:43:08

link

壹：构造最大直径

首先要考虑，当序列被确定之后，最大长度怎么计算
我们定义叶子节点为度数 $X=1$ 的节点
有一个显然的情况，即把所有非叶子节点串式项链，然后把叶子节点插上面
设叶子节点有 $K$ 个，此时最大长度 $len=n-K+1$

贰：计数

接下来我们要考虑的是如何计数
注意到，总度数 $all$ 恒为 $2*n-2$
我们可以枚举 $K$ ，然后把 $all-K$ 分配给 $n-K$ 个非叶子节点，再乘上 $len$

怎么计数把 $all-K$ 分配给 $n-K$ 个非叶子节点的个数？
容易发现，$all-K$ 是球个数，叶子节点是盒子个数，且球相同盒子不同，盒子不能为空
容易得到组合数 $\binom{all-K-(n-K)-1}{n-K-1}=\binom{2*n-2-K-n+K-1}{n-K-1}=\binom{2*n-2-K-n+K-1}{n-K-1}=\binom{n-3}{n-K-1}$
所以 $\binom{n-3}{n-K-1}$ 即为答案

此时我们得到 $ans=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*len=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K+1)$
直接算是 $O(n)$ 的，过不掉，不过我们可以考虑对 $ \sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K+1) $ 做变换

参：优化

两个常见组合公式

吸收恒等式 $k\binom{n}{k} = n\binom{n-1}{k-1}$

范德蒙德卷积 $\sum_{i=0}^{k}\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$

可以通过组合意义理解

$ans=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K+1)$
如果 $n-K+1$ 可以转成 $n-K-1+b$ 的形式，我们就可以用吸收恒等式优化
所以有 $ans=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K-1+2)=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K-1)+2*\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}$
左边单项式可以用吸收恒等式 & 范德蒙德卷积优化，右边单项式可以用范德蒙德卷积优化
得到 $ans=\sum_{K=0}^{n}\binom{n}{K}\binom{n-4}{n-K-2}(n-3)+2\binom{2n-3}{n-1}=\binom{2n-4}{n-2}(n-3)+2\binom{2n-3}{n-1}$
可以 $O(1)$ 求出

完整来说
$ans$
$=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K+1)$
$=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K-1+2)$
$=\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}*(n-K-1)+2*\sum_{k=0}^{n}\binom{n}{K}\binom{n-3}{n-K-1}$
$=\sum_{K=0}^{n}\binom{n}{K}\binom{n-4}{n-K-2}(n-3)+2\binom{2n-3}{n-1}$