S is the smallest subtree that contains all the black vertices. You need to calculate the expected value of the white vectices in S.

It can be solved using FFT, but there is a binary search solution too.

First you could binary search over the minimum value of pair sum such that count of all pairs satisfying this criteria is more than equal to M.To find count of such elements in each binary search check, you could use 2 pointers, one for maximum and the other for minimum and get the total elements satisfying the condition. After binary search we have the minimum pair sum so that total count of all pairs having more or equal sum is at least M. Say this minimum is 'Min'.So for pair sum more than equal to Min + 1, has count less than M.Sum up all such pairs with pair sum more than equal to Min + 1. And for the remaining pairs to make the count = M, we add that Min required number of times to the answer.

No mine is greedy.

I think you could generate K dp's representing dp over different indices mod K.

Yep me.

Whenever i-k is same as i pick maximum of dp[i-1][rock], dp[i-1][paper], dp[i-1][scissor] and change ith element to '$' so that next i+k you can use any of rock, paper and scissor again.

Yeah I did: https://atcoder.jp/contests/abc149/submissions/9215384

Pretty much you separate into k strings and consider each one independently.

here is mine

the source is pretty much self explanatory i guess. here is the main idea,

if str[i]== str[i-k] //for i>k
    dp[i] = max(dp[i-k], dp[i-1])
    str[i]='0'
 else dp[i] = dp[i-1] + (points gained from current win)

Edit: complexity : O(N)

let dp[i][j] be the maximum score witch you can get if we will provide only i%k-th, k+i%k-th... i-th games and on i-th game you will use j-th hand(if j=1 Rock, if j=2 Scissors, if j=3 Paper). dp[i][j]=dp[i-k][1]+dp[i-k][2]+dp[i-k][3]-dp[i-k][j]. answer is: max(dp[n][1],dp[n][2],dp[n][3])+...max(dp[n-k+1][1],dp[n-k+1][2],dp[n-k+1][3]). code: https://atcoder.jp/contests/abc149/submissions/9217025

I used FFT to find all possible sums from array A and B and then picked up the required number of elements from the sum from last. A