How to find the longest (in terms of sum of weights) simple path with at most $k$ edges in a tree? Weights of edges are integers, so they can be negative. I thought about using Bellman-Ford, but it would take too much time. Is there any faster algorithm than $O(V \cdot E)$?
Have you tried looking at the Shortest Path Faster Algorithm (SPFA)? Even though its worst case time is the same as for Bellman-Ford, the average time complexity on a random graph is $O(|E|)$ and it also works for graphs with non-negative edges.