What we are doing is for every parent child edge we are maintaining the condition that the difference of their values should not be odd and as we are using a dfs this conditions will be maintained for every edge that's what we want for the given tree, and if we try about optimality in terms of time complexity we are traversing every node at max once so it will be O(n) and to maintain condition we can see that the major increment of pointer is when when the diff is currently 2/3/5/7 so at max it will be 3-4 times in worst cases so total time complexity can up to O(3*n) in worst of worst case which is acceptable under constraints. I hope its clear now if still any doubt do let me know.
@@BitToByte1 Well thx, it means a lot I got it now. I did the dry run of different examples by making the different types of trees as well. Basically we are ensuring to have diff of either 1 or 2 or at max 4. It won't go over that for a edge ui to vi.
Could u please tell whats the intuition for D problem like how we are making sure this would give optimal answer???
What we are doing is for every parent child edge we are maintaining the condition that the difference of their values should not be odd and as we are using a dfs this conditions will be maintained for every edge that's what we want for the given tree, and if we try about optimality in terms of time complexity we are traversing every node at max once so it will be O(n) and to maintain condition we can see that the major increment of pointer is when when the diff is currently 2/3/5/7 so at max it will be 3-4 times in worst cases so total time complexity can up to O(3*n) in worst of worst case which is acceptable under constraints. I hope its clear now if still any doubt do let me know.
@@BitToByte1 Well thx, it means a lot I got it now. I did the dry run of different examples by making the different types of trees as well. Basically we are ensuring to have diff of either 1 or 2 or at max 4. It won't go over that for a edge ui to vi.