I got 100 in the pretests.
Wealth Disparity was pretty straightforward.
The main thing in this problem is that the difference between the weight of an ancestor of a node and the weight of the node must be maximum. This can be solved using DFS by maintaining another variable in the stack which represents the maximum ancestor weight encountered so far in the branch. The answer will be the maximum difference of this value and the weight of the node. This can be done by doing DFS once.
I used a vector of vector of ints to represent the tree as an adjacency list. Then DFS was done and I maintained a variable, difference which is simply the maximum value of the difference of the weight of the node and the maximum weight encountered of the parent node. This value was updated every time during a node visit and the maximum weight encountered in a branch was also updated.
Overall, DFS takes O(V+E) using Adjacency list and since E = V - 1 in a tree, Time complexity is O(2V-1) = O(V) = O(n).
Space Complexity in the adjacency list is also O(V+E) = O(V) = O(n)
For brackets, I tried brute force but got only 3/5 test cases correct in the first subtask. Does anyone have any idea how to get a non brute force solution to Brackets?
Is the cut off going to be 100 as well this time? This is my first time and I was hoping to qualify. Now though, I’m not so sure.