VOCV - Con-Junction
can’t figure out how to solve subtask 2(Find the total number of such optimal lightings in the city).
Help.
I solved both first and second subtasks together. Here’s what I did:
To solve the first subtask, I maintain 2 arrays dp1 and dp2. dp1[i] gives the minimum number of lights in i’s subtree when the junction i is lighted and dp2 gives minimum when junction i isn’t lighted.
I calculate the number of ways along with dp1 and dp2 calculation. ways1[i] and ways2[i] give number of optimal lightings when ith junction is lighted and isn’t lighted respectively.
Try to derive the recursive formulas now, it is fairly simple. You can refer to my code here - https://ideone.com/uPh7Ju
1 Like
got it 
thanks