Hello and thanks for reading this.

Given a undirected tree of N vertices and e edges with associated reward point P_e, start vertex : s and an integer : M

Then we have to find : Max no of points we can gain by starting at s and traversing M edges.

An edge can be traversed multiple times.

Please guide me in right direction to solve this problem.

# Best How To :

First of all let's observe that if you will traverse some edges multiple times in the optimal solution, then all these edges will have same reward (otherwise it's more profitable to traverse the edge with bigger reward more times). So without loss of generosity we can say that you will traverse exactly one edge multiple times.

Second of all, the edge you will traverse multiple times will be the edge with the biggest reward among all the edges in your optimal path. Otherwise again it would be more profitable to traverse the one with bigger reward more and the path would not be optimal. Thus the edge you will traverse multiple times will be the last edge in your path.

So here is a simple algorithm: look through all the vertices of the tree which are not farther than M from the starting point, find the sum of the reward points from s to each of those vertices without edge repetitions (this number will be determined in the only way because there is only one path between every pair of vertices in a tree), and use the rest of the M edges to traverse the edge with the biggest reward (every time we consider this edge is the last one we used in the current path).

You can use BFS or DFS

Here is a pseudocode:

```
ans = -INF
traverse(vertex, pathLength, pathReward, lastEdge) {
if (visited(vertex)) // Do not visit a vertex twice
return;
if (pathLength > 0)
ans = max(ans, pathReward + (M - pathLength) * lastEdge)
if (pathLength == M) // We cannot go farther than M edges
return;
for (vertex, nextVertex) in edges:
edgeReward = edgeReward(vertex, nextVertex)
traverse(nextVertex, pathLength + 1, pathReward + edgeReward, edgeReward)
}
```

You would call `traverse(0, 0, 0, -INF)`

and then get result from `ans`

.