PROBLEM LINK:
Author: ranjithganesh
Tester: ranjithganesh
Editorialist: ranjithganesh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Trees, Depth-First Search (DFS)
EXPLANATION:
The family can be viewed as a tree as given in the question and an individual’s net worth as the value of the corresponding node. One simple observation that can be made is that if the maximum difference in net worth in the tree is between nodes u and v, where v is a descendant of u, then v must either be the node with maximum value or minimum value in the subtree of u. Since the difference in values is to be considered only among its descendants, DFS can be performed which visits the root of all subtrees using recursion and returns the min-value and max-value of its subtree.
The returned min and max values of its descendants can be used to find the max difference in value with the root of the subtree. The final answer will be the maximum of the calculated value among all the nodes.
AUTHOR’S SOLUTION:
Author’s solution can be found here.