题解：[AGC069D] Tree and Intervals

zhenjianuo2025 · 2025-07-04 08:38:56 · 题解

下文中使用 S 代替题面中的 x 序列。

Rainbow_qwq 的题解里给了一个惊人的转化：将 [1,i] 中的点染黑，S_i= 同色的黑连通块数 + 同色的白连通块数 -1。

考虑不断染黑的过程，设当前黑色连通块数为 x，白色连通块数为 y，增加 i 号点后黑块数变为 x'，白块数变为 y'。

显然 x'\le x+1,y\le y'+1。

另外可以发现不可能同时有 x'=x+1 且 y=y'+1。

考虑 i 号点周围的邻居中有 p 个黑点 q 个白点。染黑 i 号点后黑块数增加了 1-p，白块数增加了 q-1。

显然当 n>1 时不可能有 p=q=0，这也说明了为什么不能同时加一减一。

进一步地，考虑 p+q=\deg u，由于开始时 x=0,y=1 结束时 x=1,y=0，因此 \sum p+q=\sum\deg u=n-1 成立，且上面保证了 \deg u\ne 0，可以想象一定可以连成一棵树，猜测这是充要条件。

现在考虑如何判定是否存在上述 x 和 y 序列。

假设 S_{i-1}=a，S_i=b。当 a\ne b 时，对于 x' 要求 1\le x'\le \min(n,x+1)；对于 y' 要求 \max(1,y-1)\le y'\le n，也就是 \max(1,a-x)\le b-x'\le n，即 x'\le b-a+x。当 a=b 时，由于不能同时顶到界，要求 x'\le x，y'\ge y。

解方程得到 x' 的取值范围是一段 [1,j] 的区间，因此记录最大值 j 即可。

设 f_{i,j,a} 表示染色 [1,i]，黑块数目最多是 j，总连通块数为 a，枚举 b 转移复杂度 O(n^4)。代码。使用一些二维差分可以到 O(n^3)。代码。