ABCDEGの6完。
A - Majority
"For"をカウントして2倍してNより大きいか。
B - Postal Card
S_iは末尾3文字しか関係ないので末尾3文字だけにしちゃう。1個でも同じのがあったらカウント（1個のS_iに対して複数回カウントしないように注意）。
C - Path Graph?
連結でない場合もあるのでかなりしんどい。さっさと連結性をチェックしておいたほうがよかったかなあ。ただそれも先が長いしな。嘘解法でもいいから通ってくれと願ってしまうタイプの問題。
まず、次数が1の頂点を見つける。それがなければNo。次数1の頂点からDFSする。子が複数あったらNo。DFSで辿った頂点数がNならYes、そうでなければNo。
D - Match or Not
問題文が読めたころには解けている。片側ずつ考えることができる。OKかNGかの2値なので情報は境界の場所だけでいい。ちゃんと実装するには時間がかかる。
E - Karuta
LCPって何だっけ。思い出してACLのstringのページを開く。ちょっと使えなさそうに見えたし普通に考えるとソートが浮かぶ。なんか証明がやりにくいけどさすがに違うの挟まってることないよねと提出。
F - Components
難しそうだけど、部分木について解けていたらと考えて、二乗の木DPっぽいと気づく。部分木の根の扱いがすぐには見えず、実装もかなりきつそう。解けるとしてもコンテスト終了近くまでかかる可能性が高く、ちょっとやりたくないのでGへ。
（追記）遷移が全然わからず、時間が経過していた。解説放送も少し聞いたのだが、計算量の説明（完全グラフの辺と対応させるやつ）を（それ自体は何回も見たことがあるけど）思い出して、処理のイメージがわいてきた。コードを書いて詰めると、主従2つの根付き木の根同士を辺でつないで主側の根だった頂点を根とする根付き木を作るというイメージが見えて、これで解けた。DFS内では、まずその部分木の根だけから成る木を作って、それと子の部分木を合体させていく。二乗の木DPってこういうのだったんだ。一回は実装経験あるからと思ってたけどなんもわかってなかった。
G - Balance Update Query
得点の順に持ちたくなる。mapとかでできそう。問題は区間の合計を知る必要があることで、そんな平衡二分探索木は持ってないけど、平衡二分探索木でできることは大抵トライ木でできるので今回もそれ。トライ木では、使用可能枚数の他に得点の合計も各ノードに持つ。細かいところでかなり手間取ったけど、最終的にはきれいにAC。
