After playing a bit with the two pieces I found that I always make them collide.

Fortunately, it suffices to randomly guess that the red piece and the blue piece will first travel to meet each other and then traverse the tree.

I still have no idea why it is the optimal solution.

After writing out the expression for a few terms, just randomly guess that the coefficient is $$$\binom{k+i}{i}$$$.

Even the tutorial skipped the proof!

Have you ever written code that you cannot explain?

Well, I have:

#include <bits/stdc++.h>

int T;
int N;
char str[210000];
char fold[420000];
char *p_fold = fold + 210000;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        scanf(" %s", str);
        std::fill(p_fold - N - 1, p_fold + N + 1, (char)0);
        int cur = 0, cur_dir = 1;
        int min = 0, max = 0;
        for (int i = 0; i < N; ++i) {
            p_fold[cur] = str[i];
            min = std::min(min, cur);
            max = std::max(max, cur);
            if (i + 1 == N) break;
            if (str[i + 1] == str[i]) {
                cur_dir = -cur_dir;
            } else {
                cur += cur_dir;
            }
        }
        printf("%d\n", max - min + 1);
    }
}

I still only vaguely know why it is correct... Good thing that Codeforces is not math but Guessforces.

Every problem from A to E is randomly guessing...

Most notably:

• D: Randomly guess that only $$$n$$$ and $$$[0, n/2]$$$ is 'Yes.'

• E: Randomly guess that you only need to divide the string into two parts.