NUTMONEY Editorial

dfs
dynamic-programming
easy-medium
nuttela
tree
tree-dp
enma2019

#1

#PROBLEM LINK:
Practice
Contest

Author: Soham Chakrabarti
Editorialist: Soham Chakrabarti

#DIFFICULTY:
EASY-MEDIUM

#PREREQUISITES:
Dynamic programming in Trees, DFS

#PROBLEM:
You are given a tree with N nodes and N-1 edges. Each node having a certain value. You need to compute the path from the root to the leaf, which has the maximum sum.

#QUICK EXPLANATION:
We can solve this problem by simple dynamic programming in trees. We run a depth first search over the tree, for every root node, we add the value of the respective child node with the greatest value only to maintain the maximum sum.

#EXPLANATION:
This is a simple DFS problem of traversing the tree and finding the maximum sum path.

dfs ( int u, int parent)
{
dp[u] = arr[u - 1]; //dp table to store the maximum sum
int maximum = 0;
for (int child : Tree[u]) {
if (child == parent)
continue;
dfs(child, u);
maximum = max(maximum, dp[child]);
}
dp[u] += maximum;
}

The dp table stores the maximum sum in it’s first index. :grinning:

This link
might be helpful.

#AUTHOR'S AND EDITORIALIST'S SOLUTIONS:
Author's and editorialist’s solution can be found
here.