Convert each 'G' to +1 and each 'H' to -1. Now the problem asks to split the array into segments such that we have minimal number of segments with positive sum and the length of each segment is  ≤ K.

We will solve this with DP. The state is dp[position] =  answer for the prefix [1;position]. It can be easily solved in by doing a sliding window with a segment tree.

Code

Main observation is that we need to find the number of pairs of cycles that are edge-intersecting. Now if we root the tree and for each cycle find the LCA of its two vertices, then for each pair of intersecting cycles the LCA of one of them w will be above (or they will have the same LCA). We will consider the case of same LCA separately. The other case can be done with a DFS + segment tree/Fenwick on DFS order. Look at the code for details. The complexity is .

Code

My solution's time complexity is , but it can be easily improved to .

Lets solve the problem for the interval (X, Y) of the K-minimums. Now find the minimum value in it. We will denote it as a[P]. Also we will extend [P;P] to the left and right while the value of a[P - 1] is the same as the value of a[P]. Now we have an interval [L;R] such that everything in it is equal to the minimum value.

Obviously if L > X, a[L] < a[L - 1] and if R < Y, a[R] < a[R + 1]. From here we can notice that if L > X, Value[L + K - 1] should be exactly equal to MIN and all values in the interval [L - 1, L + K - 2] should be > MIN. This means that the values in [X;L + K - 2] and [L + K - 1;Y] are independent.

Similarly, but for R, we have that Value[R] should be exactly MIN and everything in the interval [R + 1, R + K] will be > MIN. And we get that interval [R + 1, Y] is independent.

So from the above two we can do the following D&C algorithm:

1) Define solve(X, Y) being the answer for [X;Y]. The answer to the problem is solve(1, N - K + 1).

2) Find L and R as described above. This can be done in time with segment tree.

3) If X < L multiply the return value of the current solve() by solve(X, L - 1).

4) If R < Y multiply the return value of the current solve() by solve(R + 1, Y).

5) Now multiply the return value of the current solve() by the number of ways to fix the values corresponding to the K-minimums in the interval [L;R]. This can be done in O(R - L) with a simple dp.

6) Return the value.

The complexity will be because of the segment tree. To reduce it to linear time, we can just find the intervals with equal values with one linear pass.

Code