k tree problem in dynamic programming

can anyone explain how to do this question Problem - 431C - Codeforces

i am not getting any logic all i am getting is recursion but it will be like TLE so kindly please help me . if you know ans plz explain it in detail