Help on a tree problem from SPOJ (EAGLE1)

problem link: https://www.spoj.com/problems/EAGLE1/

the problem in short is in a weighted tree you need to find the maximum path from each node (starting node) and you don’t cross a node twice in a single path.

Refer to the problem link for better clarifications.

I am not sure how to approach this problem. I thought about finding the maximum path that exists in the tree but that will be answer for only starting and ending node in that path. Time limit is short i don’t think it will be a O(n^2) problem. I found it in a list of dfs problems. Other problems were easy. So am I missing something?
If anyone can suggest the correct approach it will be helpful.

1 Like