Given a undirected graph(Total No of Nodes is 1e5) .each node has its beauty .each edge has its own 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.Please confirm if it is Np-hard problem (As i correctly remember this was asked in coding test )

Thanks