Please tell me what am I doing wrong, accroding to the way you suggested!! lets work for the sample testcase: 3 3 1 2

i.e. tree has 3 nodes (1,2 and 3 such that, 3 is child of 2 and 2 is child of 1).

dp1[1]=1 (number of ways to assign numbers<=1 to tree of 3 nodes). dp1[2]=2*2*2=8 (number of ways to assign numbers<=2 to tree of 3 nodes). dp1[3]=3*3*3=27 (number of ways to assign numbers<=3 to tree of 3 nodes).

dp[1]=dp1[1]=1; dp[2]=dp1[2]-dp[1]*(2c1)=8-2*1=6 (whre 2c1 means binomial coeficent of 2,1) dp[3]=dp1[3]-(dp[1]*(3c2)+dp[2]*(3c1))=27-(1*3+6*3)=6

now answer=3*dp[1]+3*dp[2]+1*dp[3] (since D is 3) =3*1+3*6+6=27 But the answer stated in sample case is 10.

Any help? I did the same as stated in your solution.

Could you please elaborate !!!

please explain a bit about the dynamic programming approach for this problem...how can you traverse all the childs of i without traversing it again... suppose i has 2 branches then after travelling the first branch in graph, we must return to i to move to second branch.. thus how is patrol[i] is defined in those cases where the parent has more than 1 child.