Divine number as I understood : It is written that for every Ri cities there exist a city that is connected to all of them. And for the 2nd test case : For every pair of city there exist atleast one other city which is connected to all of the selected cities directly.
Dp states : once the divine numbers are built we can find the value of the minimum path length from all the nodes considering only it’s subtree i.e. path length when we go to all the available cities in the plan that are present in the sub-tree of the current node. Apart from this I also have calculated bck[i] for all the nodes which denotes how much distance we have to travel more if we want to come back to the root again (important info when we have to cover rest of the cities outside the current sub-tree). For calculating this I sort all the values for all the branches and just select the maximum (as for minimum length to visit all the nodes we have to go to all the branches one by one and we have return from all of them except from the last one which we may choose to be the longest one.).
Similarly for the out_States I used the in_States info. and just calculate the same two things out[i] and bck_[i] . If you want I can explain it more.
PS : I don’t know whether the approach or the way I calculate the divine number is correct or not as my code doesn’t ACed at contest time due to some bugs which I fixed after the contest. Even though I am not sure whether it will pass or not. So, if you get correct solution or a valid proof for divine number then plz plz explain.
UPD : I didn’t get AC.
. If you got the solution then please share.