Given a undirected graph(Total No of Nodes is 1e5) .each node has its beauty .each edge has time travel cost .U have some finite time say m(<=100).U are at root node of graph.U have to travel those nodes and return to root .find the maximum beauty that u can collect. Idea is by knapsack .But I am facing difficulty in calculating dp states.

Thanks