k tree problem in dynamic programming

can anyone explain how to do this question http://codeforces.com/problemset/problem/431/C

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