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, l_i and r_i are the left and right child of i and s_i 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?