CF1682D Circular Spanning Tree 做题记录

有 $T$ 组数据，每组数据有一个长度为 $n$ 的 $\tt 01$ 字符串，求构造一个 $n$ 个结点的树满足每个结点的度数的奇偶性符合 $\tt 01$ 串 $s$，且将这些点依次排列到一个环上，任意两条边不在非端点处相交。

$1\le n\le 2\times 10^5$。

VP 的时候想到了一大堆奇奇怪怪的做法，有些是对的，但是都否定了。

首先发现因为每条边都会贡献两个度数，又有 $n-1$ 条边，所以若度数总和是奇数那么就不行。

由于需要构成一棵树，而树的叶子节点一定只有一个度，所以若度数全都是偶数也不行。

对于其它情况，考虑构造解：

1. 若度数都是奇数，那么此时 $n$ 必定为偶数，把 $1$ 当作根，其它点向 $1$ 连边组成菊花图即可；

2. 否则考虑构造一些链，把整个序列看作一个环，把环断成 $k$ 段 $[0,0,0,\dots,1]$ 这样的序列，每一段序列都依次串起来，这样我们就获得了一些”趴在边上“的链。考虑如何把这些链连起来，显然由于度数是偶数，$k$ 一定是也偶数，所以拿一条链的开头当作根把这些链接上即可。