所以我有一个如上所述的问题。我在想一些dp，但我不是很擅长…
示例：5个顶点，连接对：(1，2((1，3((3，4((3，5(
每个顶点(和路径(的答案：1:2(1-3-4(2:3(2-1-3-4(3:2(3-1-2(4:3(4-3-1-2(5:3(5-3-1-2(
我假设的是无向树。
如果你想让每个顶点v显式地找到从v开始的最长路径，那么从每个顶点开始的BFS/DFS就很好了，因为最长路径的总和可能高达n2(如果你喜欢这样称呼的话，这是一个退化树，就像一条线或分支(。由于内存消耗是每个算法的下限，因此在最坏的情况下，算法的运行时间将为Θ(n2(。
如果你只想要最长路径的值，我建议你阅读这篇关于树上动态编程的文章，特别是问题Tree Distances i的解决方案，因为它与你所要求的完全相同。YouTube上甚至有一个解释，c++中也有一个公认的代码示例。