問題文 : 友だちをつくろう

問題文 : ABC-Strings概要 : 文字列 $S$ の部分文字列 $t$ であって, $t$ の中の A の個数, B の個数, C の個数が等しい物の個数を数えよ.制約 : $1 \leqq |S| \leqq 10^6$ $S$ は A, B, C だけからなる文字列である.

さたしゅんくん とUTPC 2013 に, チーム†背徳ト絶望ノ番人†で参加し, 16 位を収めました. ということで時系列でコンテストを振り返ってみます. コードは後で載せます. 進捗ダメです.

問題 : Coloring Tree概要 : $n$ 頂点からなる根付き木のそれぞれのノードに色がついている. 頂点$v$ を根とする部分木にある, 異なる色の個数を数えるクエリに$m $ 個答えよ.$1 \leqq n \leqq 10^5$ $0 \leqq m \leqq 10^5$ $1 \leqq v \leqq n$ $1 \leqq$ …

が 以上の整数のとき,となることを示せ.この問題の証明をしている方がいて, 解答をすぐに追えなかったので反省を込めて自分でも証明を書きます.