题解：[AGC069D] Tree and Intervals

下文中使用 $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)$。代码。