小白 44 F 题题解

张果老——醉酒抛杯踢连环

Back $\Leftarrow \backslash Leftarrow$

问题模型

你获得了 $nn$ 条链，第 $ii$ 条链的长度是 $a_{i}a\_i$。

给这 $\sum a_i\backslash sum\; a\_i$ 个点再连上 $n-1n-1$ 条边，使得它们构成一个包含 $\sum a_i\backslash sum\; a\_i$ 个结点的“大树”。

请输出最终 可能 成为“大树”重心的结点的个数。

模型分析

对于第 $ii$ 条链的第 $jj$ 个结点（以下简称点 $(i,j)(i,j)$）：

• 首先很明显根据“重心”定义，最优策略是把剩下 $n-1n-1$ 条链全部作为子树挂上去。

• 进而分析有解的条件，也就是说：

• 记 $x=j-1,y=a_i-jx=j-1,y=a\_i-j$（第 $jj$ 个点之前、第 $jj$ 个点之后的结点数）

• 所以 $a_1,a_2,\cdots ,a_{i-1},a_{i+1},\cdots ,a_n,x,ya\_1,a\_2,\backslash cdots,a\_\{i-1\},a\_\{i+1\},\backslash cdots,a\_n,x,y$ 共同构成点 $(i,j)(i,j)$ 的子树。

据此只需要判断：

$\max \{a_1,a_2,\cdots ,a_{i-1},a_{i+1},\cdots ,a_n,x,y\}\le \lfloor {\displaystyle \frac{\sum a_i}{2}}\rfloor \backslash max\backslash \{a\_1,a\_2,\backslash cdots,a\_\{i-1\},a\_\{i+1\},\backslash cdots,a\_n,x,y\backslash \}\backslash le\backslash left\backslash lfloor\backslash dfrac\{\backslash sum\; a\_i\}\{2\}\backslash right\backslash rfloor$

不妨考虑拆解这个式子：

$\{\begin{array}{c}\max \{a_1,a_2,\cdots ,a_{i-1},a_{i+1},\cdots ,a_n\}\le \lfloor {\displaystyle \frac{\sum a_i}{2}}\rfloor \\ \max \{x,y\}\le \lfloor {\displaystyle \frac{\sum a_i}{2}}\rfloor \end{array}\backslash begin\{cases\}\backslash max\backslash \{a\_1,a\_2,\backslash cdots,a\_\{i-1\},a\_\{i+1\},\backslash cdots,a\_n\backslash \}\backslash le\backslash left\backslash lfloor\backslash dfrac\{\backslash sum\; a\_i\}\{2\}\backslash right\backslash rfloor\backslash \backslash \backslash max\backslash \{x,y\backslash \}\backslash le\backslash left\backslash lfloor\backslash dfrac\{\backslash sum\; a\_i\}\{2\}\backslash right\backslash rfloor\backslash end\{cases\}$

第一个式子可以考虑预处理除去 $a_{i}a\_i$ 之后的序列 $\max \backslash max$ 值，$O(n)O(n)$ 扫描即可。

第二个式子可以考虑对于一个 $a_{i}a\_i$ 批量计算（在满足了一式的前提下），考虑奇偶分讨：

由图示结论可得，$a_{i}a\_i$ 的贡献是：

• $a_{i}a\_i$ 为偶数：$\min (\lfloor {\displaystyle \frac{\sum _{j\mathrm{\ne }i}{a}_j}{2}}\rfloor \times 2+2,a_i)\backslash min\backslash left(\backslash left\backslash lfloor\backslash dfrac\{\backslash sum\backslash limits\_\{j\backslash ne\; i\}a\_j\}\{2\}\backslash right\backslash rfloor\backslash times2+2,a\_i\backslash right)$

• $a_{i}a\_i$ 为奇数：$\min (\lceil {\displaystyle \frac{\sum _{j\mathrm{\ne }i}{a}_j}{2}}\rceil \times 2+1,a_i)\backslash min\backslash left(\backslash left\backslash lceil\backslash dfrac\{\backslash sum\backslash limits\_\{j\backslash ne\; i\}a\_j\}\{2\}\backslash right\backslash rceil\backslash times2+1,a\_i\backslash right)$