I was trying to solve problem A from the recently conducted ICPC regional contest.
My approach was to use the following DP transition state — dp(i)(j) denotes the number of ways to assign labels to the subtree rooted at node i such that node i is given the label j.
I came up with the following transition for this state
where 
is the binomial coefficient, li and ri are the left and right child of i and si denotes the size of the sub-tree rooted at i.
According to me the time complexity of this algorithm is 
if I use prefix and suffix sums in the summation but it seems that this solution gets accepted. Can someone help show me how?
WLOG, assume sli ≤ sri. Also, notice that k ≤ sli.
Also, si = sli + sri + 1 = O(sri)
Then, total number of computations
Notice that
Aaah so you iterate over the smaller subtree. That makes a lot more sense now. Thanks! :)