HackerRank Coding Interview 9. Rooted Distances — Part 2— Answer

After u have practiced the question, its important to understand the answer and how it resolves better.

Skills: Trees, Dynamic Programming

Optimal Solution:

​

This problem can be solved using the concept DP on trees. Assume that the tree is rooted at node 1. We will solve for a subtree, store its answer in dp[v] and store the sum of all nodes in subtree of vertex v as sum[v]. Then the answer for a vertex u is simply the sum of dp[child] + sum[child] over all children of u. Finally, dp[1] will denote the beauty of v = 1, so we can easily propagate these values to its children recursively. (you can learn more about rerooting-dp from here) Finally, we take the maximum of dp[v] over all vertices. Since in DFS calls we are going through each node and edge once Time complexity will be O(V+E) and as we are storing adjacency list of our graph Space complexity will also be O(V+E) where V is number of vertices and E is the number of edges.

e.g. https://www.youtube.com/watch?v=3UXK0Mab5fM

long maxBeauty(int tree_nodes, vector<int> tree_from, vector<int> tree_to, vector<int> a) {
    vector<vector<int>> g(tree_nodes+1);
    for(int i=0;i<tree_nodes-1;++i) {
        int x = tree_from[i], y = tree_to[i]…