#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.

This link

might be helpful.

#AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialistâ€™s solution can be found

here.