2023/12/03(#4)：这世界突然填满，色彩

这就是，这个世界啊。

懂得都懂。

[APC001E] Antennas on Tree

Portal.

不难发现只有一个点为根的子树中有两个以上的没有选择点的时候坐标会算重，那么从度数为 $1$ 的点随便 DFS 一下即可。代码。

[AT_cf17_final_j] Tree MST

Portal.

直接点分治，然后合并的时候再跑一次 Kruskal 就可以了。代码。

[Ynoi2013] 对数据结构的爱

Portal.

考虑模拟这个过程。我们需要知道对于一段区间，到底会减去多少个 $p$。

搞一个数组 $c_i$ 代表这段区间要减去 $i$ 个 $p$ 的最小初始值，那么查询的时候直接二分就行。现在考虑如何计算 $c$ 数组。

尝试枚举左儿子的 $c_x$ 和右儿子的 $c_y$ 来计算 $c_{x+y}$，什么时候不能更新？$c_x$ 的上界经过操作后依然小于 $c_y$。

用 $\max\{c_x,c_y+x\times p-sum_{ls}\}$ 更新 $c_{x+y}$。由于 $c_{x+1}-c_{x}\ge p$，因此直接双指针扫就行。

单次询问会拆成 $\log$ 个区间，每个区间用 $\log$ 时间二分，时间复杂度为 $O(n\log n+m\log^2 n)$。代码。

[AGC061B] Summation By Construction

Portal.

首先明确我们到底要干什么。对于颜色 $i$，$i$ 个左部点都各连两个连续的右部点即可。

$n$ 为奇数时，不难按照 $i+j=n$ 构造出方案。

$$\begin{bmatrix} 3 & 3 & 2 & 2 & | & & \\ & 3 & 3 & 2 & | & 2 & \\ & & 3 & 3 & | & 1 & 1 \end{bmatrix}$$

偶数向下扩展就可以了。

$$\begin{bmatrix} 4 &4 & & &\color{red}{2}\\ \color{red}{1} & 4 & 4 & &\color{red}{1}\\ \color{red}{2}& 3 &4 & 4 &\color{red}{2}\\ \color{red}{2}& 3&3& 4 & 4\\ -&-&-&-&-\\ &&3&3&\\ &&&3& \end{bmatrix}$$

代码。

ED

好摆好摆好摆好摆好摆好摆好摆好摆好摆好摆好摆。