题解：AT_ddcc2017_final_d なめらかな木

· · 题解

提供一种（口胡起来）完全不需要动脑子的线性做法。

首先考虑一条链的答案，如图：

左边是链在两端折起来的两种情况，右边是链在中间叠起来的情况。

令 \text{calc}(n,x,y) 为一条长度为 n 的链，左/右边长度为 x/y 的一端折起来的方案数。容易发现可以自由进行“叠起来”操作的“自由点”数量为 n-(x+0/1)-(y+0/1)，其中 0/1 代表下面的折法还是上面的折法。容易递推求出“自由点”“叠起来”的方案数。那么只需枚举"自由点“数量即可算出链的答案。

然后考虑加入一些四度点，如图：

发现相当于将两条链分别“嵌入”左右。同时注意到所有的四度点一定在一条链上。那么可以把这条链给拎出来，按照一个顺序对四度点 dp。具体地，第 i 个四度点到第 i+1 个四度点之间的“主链”长度和嵌入的链长度与方法（有没有多吞掉一个自由点）只有 O(1) 种，直接开 map 记下来就可以了。左右两端可能需要一定的特判。

接下来考虑加入三度点。一个 naive 的想法是把三度点看成是四度点的一条链退化成长度为 0 的情况，但是发现漏了情况，如图：

漏的第一种是这样的，三度点的左右同属于一条链，用一定的特判可以补救。

但是注意到，那个绿色点也可以是三度点，如图：

那么就得把相邻的两个点往后转移一下了。

那我们做完了。。。吗？

发现黑色边可以接上另外的三度点，如图：

这个时候三四度点已经不一定在一条链上了，但是还可以补救一下。注意到可以找到一条链使得所有三四度点距离它的距离不超过 1。我们取出这条链（可以看作是直径），认为不在链上的三度点如上图所示被捆绑在了距离它为 1 的三度点上，那么只有直径端点的捆绑可能有问题，稍微讨论亿点点情况即可。

那么这道题大概率（因为数据好像并不是很强，认为三四度点都在一条链上只有一个点过不去）就做完了，复杂度是线性的。

Submission，如果有 hack 可以联系我。