1695E

一道Div2 的 E(last) 题

一直想错解，一直做不对，我很是生气，我觉得我是个弱智。

首先肯定是连边建出图，不难发现一种构造是我们拿出这个图中的一条>=2链，然后交错一位放即可。 \[ \begin{bmatrix} a,&b,&c,&d\\ b,&c,&d,&e\\ \end{bmatrix}=(a,b)+(b,c)+(c,d)+(d,e) \]

这样就启示我们要把原图划分成若干 >=2 的链。

但是这回存在一种一个三度点的菊花，这是不可能被若干>=2的链覆盖的。

我最开始甚至以为这个无解，但实际上存在构造。 \[ \begin{bmatrix} a,&b,&a\\ c,&a,&d\\ \end{bmatrix}=(a,b)+(a,c)+(a,d) \] 我最开始的思路是要把这两种构造拼起来。事实上这样也是可行的，我们对每个点的度两两匹配。

考察剩下的，剩下的就是对于一条3元链，我们只可能有 \(O(1)\) 中情况，不难手玩出来都是合法的。

但是这个 \(O(1)\) 情况还是太多了，我们实际上并没有简化这个问题，尽管只有 \(n\leq 5\) 个点，但是我依然不会构造，。。。。。。

上面说的是原问题不难于 \(n\leq 5\) 的。同时也说明了无论怎样的一张图都是有解的。

所以其实我们可以拆一些边，建一些虚点把这个图变成树。

也就是说，原问题是不难于树的情况。接下来考虑树的构造。

树的构造很经典，因为每个点必须只有一个父亲，所以可以让他的儿子匹配，如果剩下的就和连向父亲的边匹配。

这样在根节点讨论即可。。。。。。

抢到了114/cy