给定一棵树，为每个顶点找到到其他顶点的最长路径
GIven a tree, for each vertex find longest path to other vertex
所以我有一个如上所述的问题。
我正在考虑一些 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)。
如果您只想要最长路径的值，我建议您阅读 this post about dynamic programming on trees, specifically the solution to problem Tree Distances I as it's identical to what you ask for. There is even an explanation in YouTube and an accepted code example in c++。
所以我有一个如上所述的问题。 我正在考虑一些 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)。
如果您只想要最长路径的值，我建议您阅读 this post about dynamic programming on trees, specifically the solution to problem Tree Distances I as it's identical to what you ask for. There is even an explanation in YouTube and an accepted code example in c++。