CF1682D Circular Spanning Tree 做题记录

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

1n2×1051\le n\le 2\times 10^5

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

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

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

对于其它情况,考虑构造解:

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

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