最长路径

[编程题]最长路径

热度指数：1809 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

城市 $A$ 新建了 $n$ 个座房子，城市规划处用 $n-1$ 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。

示例1

输入

7,[2,3,5,4,5,5],[5,2,1,6,7,4],[15,6,14,4,1,6]

输出

说明

当牛牛和牛妹分别被分到  ,  两个房子时，路径最长。

备注:

房子  , 房子  , 街道长度 。
表示房子  与房子  之间有一条长度为 的道路相连。
 。

算法知识视频讲解

未来0116

发表于 2021-08-10 08:51:57

一.题目描述NC537最长路径城市A新建了n个座房子，城市规划处用n−1条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。二.算法(dfs)题目意思我们理解后，我们知道要求求出两个房子直接的最长距离，在图展开全文

认认真真coding

发表于 2021-08-03 18:26:51

题目描述城市 A 新建了 n 个座房子，城市规划处用 n−1 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。方法一：暴力解法求解思路对于求解本题，我们可以将房子看作节点，双向街道看作边，即n个节点展开全文

十里阳光

发表于 2021-03-20 13:27:38

使用深度优先遍历没看到详细题解，自己写一个 == 先使用邻接表存储深度优先遍历，求解所有路径最大值和代码如下，有注释class Solution: def solve(self , n , u , v , w ): # write code here def df 展开全文

AimerAimer

发表于 2021-10-11 13:35:05

题意：求一棵树的最长路径，即求树的直径。 &n 展开全文

摸鱼学大师

发表于 2021-08-06 16:27:38

思路：题目的主要信息： n个节点，n-1条边，使之全部连通，这就是一棵树树中任意节点的路径最长值，就是求树的直径首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。方法一：两次深度优先搜索具体做法：我们需要用哈希表来存储树的边结展开全文

牛客313925129号

发表于 2021-08-08 18:14:46

题意理解 n个房子对应于n个结点，街道就对应于结点之间的边，构成一张连通图。找到这张图中哪两点之间边上的数值之和最大。方法一深度优先搜索使用二维数组path存储路径的信息，对于每一个点，要记录它和其它结点所有路径的长度。然后以每一个点分别作为起点，都进行一次深度优先搜索，每走一步都更新一次最长路展开全文

Bug-Maker

发表于 2021-07-09 01:17:46

1、随机选择一个点进行深度搜索，找到最长长度的尾节点，此尾节点必定为所求的最长路径的头节点（或尾节点，因为是无向图，最长路径的头节点也可以是尾节点）。推导过程：https://zhuanlan.zhihu.com/p/44391252。2、从第一步找到的尾节点出发再找一次最长路径，就是结果。 cla 展开全文