Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022

　Cまで三完。約20分遅れで書き終ったEはコンテスト後、ACしました。その後、剽窃が発覚しunratedに。

コンテストへのリンク
コンテスト後のツイート

C (()())(())の三個目の(では答えが増えないが、五個目の(では増える。一つ下のレベルのカッコが閉じれば、また答えが増えるようになる。
E (i,i+1,j,j+1)という四つ組か(i,i+x)という組かそれ以外かのなる。四つ組を何個作るかで場合分け。四つ組の作り方や、残りで二つ組をいくつ作れるかは事前にDP

— titia (@titia_til) September 6, 2022

 D. Edge Split

　解説AC。

　これを飛ばす判断は間違ってなかったと思う。

　赤、青それぞれが連結な木になるよう色を塗れば良い、と思い、それをどう実装すれば良いか分からなかった。

　が、実際は連結性はいらなかった！　赤、青それぞれが森になっていればOK。

　実装はDFS木の性質を使うと良い。

　DFSで全域木をとって、残り三辺がサイクルになると困るが、DFS木の後退辺が親子関係にあるので、サイクルの一辺の色を変え、代わりに根へ付け替えれば良い。

　（という説明は、tatyamさんのツイートそのままです。これを思いつかないと実装で迷走しそう）