I was going through the tutorial 1111 E Tutorial and I'm finding it hard to understand the dp equation given :

dp[i][j] = dp[i-1][j]⋅(j-h[i]) + dp[i-1][j-1]

(I am putting my understanding and it might be wrong. Do correct if i'm going wrong.)

So, I understand that dp[i-1][j-1] means that we are dividing the first i-1 people into atmost j-1 groups and just allocating the ith person to a newer group.

I am finding difficulty in the first part : dp[i-1][j]⋅(j-h[i])

j-h[i] mean that after allocating the first i-1 people into atmost j groups, we can now allocate the ith person only into those groups which do not have ancestors(present in the query) in that group.

Suppose that the tree is

1-2-6-4-5-3 | 7 and query elements being 2, 3. So, h[6] = 1(which is element 2 because 2 is the ancestor of 6 and 3 is not);

Let's say for element 6, and j=3 we can allocate 1 and 2 in different groups. So, 1,2 will take up 2 groups (dp[i-1][j-1] = 2) and now for allocating 6, we can add 6 in dp[i-1][j]*(j-h[i]) ways.

Can anyone explain to me what will be the value of dp[i-1][j]*(j-h[i]) here.

According to me dp[i-1][j] will be 2 because still, we can allocate the first 2 elements(1,2) into atmost 5 groups in 1 way(2 groups). and value of j-h[i] will be 3-1=2. So, 1*2=2 ways. Can anyone tell me what are those 2 ways?

In above example j-h[i] means that we have atmost 3 groups(Is it 3 grps or 3 non-empty grps (I'm in doubt)!!) and we have element 2 as the ancestor of 6 in the query, so we can't put 6 with 2. Hence we can put 6 with 1 and leave 2 alone OR we can put 1,2,6 each in a different group, but we have included the later case in dp[i-1][j-1] case.

Hence, there is only one way of allocating element 6(ie- with element 1) and leaving element 2 alone in a group.

So, Aren't we calculating j-h[i] in a wrong way? Kindly help me with this doubt.