[ARC142D] Deterministic Placing

前言

本文思路与此博客一样，部分引用已经过本人授权，不过他不想写了，所以我帮他完善/修正一下。

思路

首先观察一下合法的情况 S 满足什么条件，显然在这种情况下 S 能且仅能转到一种状态 T，同时 T 也只能转到 S，我们将用过的边染为红边，没用过的边染为黑边，选的点为黑点，没选的为白点，如下图所示

对于一条链来讲，肯定是一个白点加一堆黑点且链长度必须大于一，我们记这条链的白色点为头，最后面的黑色点为尾，中间的为身子，注意身子可能并不存在。

容易发现一些性质，头和尾显然只会连接一条红边，若只保留黑边的话，头只能连尾，尾只能连头，身子只能连身子，也就是说不然 S 到 T 后将面临无法划分的情况，如果不理解建议读者自行画图理解。

考虑树形 DP，有以下 7 个状态：

转移也就是：

• f_{x,0}= \prod_{y \in son_{x}} f_{y,3}
• f_{x,1}= \sum_{y \in son_{x}}(f_{y,4}+f_{y,2}) \prod_{z \ne y}f_{z,3}
• f_{x,2}=\prod _{y \in son_{x}} f_{y,1}
• f_{x,3}= \sum_{y \in son_{x}}(f_{y,5}+f_{y,0})\prod_{z \ne y} f_{z,1}
• f_{x,4}= \sum_{y \in son_{x}} (f_{y,2}+f_{y,4}) \prod_{z \ne y} f_{z,6}
• f_{x,5}= \sum_{y \in son_{x}} (f_{y,0}+f_{y,5}) \prod_{z \ne y} f_{z,6}
• f_{x,6} = \sum_{y \in son_{x},z \in son_{x},z\ne y} (f_{y,0}+f_{y,5})(f_{z,2}+f_{z,4}) \prod_{k \ne y,k \ne z} f_{k,6}

这个显然是会超时的，考虑优化。