algorithm - Find path of given length with max weight or gain starting from source node -

hello , reading this.

given undirected tree of n vertices , e edges associated reward point p_e, start vertex : s , integer : m

then have find : max no of points can gain starting @ s , traversing m edges.

an edge can traversed multiple times.

please guide me in right direction solve problem.

first of let's observe if traverse edges multiple times in optimal solution, these edges have same reward (otherwise it's more profitable traverse edge bigger reward more times). without loss of generosity can traverse 1 edge multiple times.

second of all, edge traverse multiple times edge biggest reward among edges in optimal path. otherwise again more profitable traverse 1 bigger reward more , path not optimal. edge traverse multiple times last edge in path.

so here simple algorithm: through vertices of tree not farther m starting point, find sum of reward points s each of vertices without edge repetitions (this number determined in way because there 1 path between every pair of vertices in tree), , use rest of m edges traverse edge biggest reward (every time consider edge last 1 used in current path).

you can use bfs or dfs

here pseudocode:

ans = -inf  traverse(vertex, pathlength, pathreward, lastedge) {     if (visited(vertex)) // not visit vertex twice         return;     if (pathlength > 0)         ans = max(ans, pathreward + (m - pathlength) * lastedge)     if (pathlength == m) // cannot go farther m edges         return;     (vertex, nextvertex) in edges:         edgereward = edgereward(vertex, nextvertex)         traverse(nextvertex, pathlength + 1, pathreward + edgereward, edgereward) } 

you call traverse(0, 0, 0, -inf) , result ans.