o の隣は無条件に . に書き換えておいた。DP をするのかな復元するのかなどうやるのかなと最初は考えていたけど、出力が必然の o か . かそれ以外の ? かということで、２通りの可能性があるなら即座に ? が決定するのだった。最終的に見つかった条件は、「? を１つ以上 o に変えるかどうか」「? を最大限 o に変えなければいけないかどうか」「(最大限 ? を o に変えるとして)連続する ? の個数が偶数か奇数か」というものだった。これで T が決まる。方針を定める時間と考えながら実装する時間で 30 分かかった。■E 問題 Reachable Set。不可能なケースがあるのかなとまず考えた。ある。サンプル２がそうなんだけど、頂点５を経由しないと頂点１と２が連結にならないので、k=2,3,4 が -1 (不可) になる。じゃあ使える辺を使ったときに 1-k までが連結かどうかを UnionFind で管理したいね。同時に、使えない辺の先に繋がっている消したい頂点の集合を管理したいね。同時にできる？ できる。14 分かけたので D の半分。■F 問題 Add One Edge 3。直径の候補は木１の直径と、木２の直径と、i-j を結んで新しくできた i-j を通る直径の３種類だと思った。木の直径は DFS ２回で求まる。新しくできる直径は、各頂点について最も遠い頂点がどれだけ遠いかわかっていればわかる。それは全方位木 DP で求まる。２回の DFS を２つの木に対して合計４回やると、２秒を超えてしまって TLE だった。なにかへまをしていて５秒 10 秒かかるようなスクリプトになっているなら惜しくはないけど、制限時間が３秒だったら通っていたというならあまりにも残念。■コンテスト成績証。ぴったりギリギリで青パフォ。973 位だから「３桁順位に入りたいよー」と書いていた前回の雪辱は果たせたけど、最近落ち目なのだから今日くらいはもっと調子に乗らせてほしかった。