题解：AT_arc142_d [ARC142D] Deterministic Placing

· · 题解

[ARC142D] Deterministic Placing

一开始看错题意猜了一个结论，然而这个结论是正确的但在原题限制我不会证。。。

下文中没有指代的连通块默认指黑点组成的连通块，黑点指有棋子的点，白点反之。

这种数数题肯定先手玩找一下性质，首先可以发现只需要 k=1,2 的时候满足对于任意 k 都是满足的。

接下来考虑一下合法方案的黑点连通块的形态。首先考虑在链上的情况，将黑点组成的段提出来，那么相邻两个段之间的白点数量一定只有一个，否则一定不符合题目要求（因为这样可以往两个方向移动）。

实际上我们可以将一个白点并入到一个黑点段中去，这样每一段都一定在两端有正好一个白点，而如果我们确定了并入白点之后的段的位置，那么染色方案只有在第一段的开头还是结尾染这两种，因为不能出现相邻的白点。而此时我们只需额外保证每一段的长度大于等于 2 即可。

用同样的思路分析树上的问题，可以猜一手是在树上分成若干不相交的链连通块，并且满足上述条件，但此时会存在一些问题。可以发现如下的情况是合法的：

此时蓝色和绿色的点对应这两条分出来的链，其中每条链有一个端点为白点，此时如果绿色链中的点移动到蓝色点，那么蓝色点将无法移动，所以这两个链只能在内部移动而每个链白点位置独立，所以有 4 的系数。

继续观察，可以发现如果黑点连通块不为链那么划分出来的链的相交位置一定不能是一个链的端点和另一个链的非端点。否则将端点的那个链移动后非端点的链上的点可以填充进那个移走的位置。

那么就可以考虑 dp 了。设 f_{u,0/1/2} 分别表示 u 子树内，u 为一条向上链的链端点但该链还未结束、u 是一条向上链的端点并且该链已经结束和 u 是链的深度最浅的点的方案数。

对于 0，此时其可以是一条链最下方的一个点或中间点，并且其为中间点是可以和中间点连边，所以转移为：

f_{u,0}=\prod_{i\in son_u} f_{i,1}+\sum_{i\in son_u}f_{i,0}\prod_{j\in son_u,j\neq i}2f_{j,2}

上面有一个系数 2 是因为一条链有两种放白点的方法。

对于 1，此时链是结束位置，而且其只能与链端点有边，所以转移为：

f_{u,1}=\sum_{i\in son_u}f_{i,0}\prod_{j\in son_u,j\neq i}f_{j,1}

对于 2，此时需要选择两个儿子连接，转移：

f_{u,0}=\sum_{i\in son_u}\sum_{j\in son_u,j\neq i}f_{i,0}f_{j,0}\prod_{k\in son_u,k\neq i,k\neq j}2f_{k,2}

用类似背包的东西递推一下就是 \operatorname{O}(n) 的了，可以通过此题。