Maximize profit on un-directed tree.

See more:

algorithm

trees

graph

I came across this problem while giving a sample test. The problem was that we have given a tree which is undirected. We can start from any node of our choice. Initially we have power "P" and while going from one node to other node we loose some power "X" (consider as cost of travelling) and earn some profit "Y". So we need to tell that what is the maximum profit that we can earn with a given power ?

Example: First line contains number of nodes and initial power

Next n-1 lines contains node-node-cost-profit

5 4

1 2 1 2

1 3 2 3

1 4 2 4

4 5 2 2

Answer => 7. We can start from 4 and go to 1 and than to 3.

What I have tried:

I applied DFS by checking every single path but is there a way to solve this problem more optimally.