leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你两棵 无向 树,分别有 n 和 m 个节点,节点编号分别为 0 到 n - 1 和 0 到 m - 1 。给你两个二维整数数组 edges1 和 edges2 ,长度分别为 n - 1 和 m - 1 ,其中 edges1[i] = [ai, bi] 表示在第一棵树中节点 ai 和 bi 之间有一条边,edges2[i] = [ui, vi] 表示在第二棵树中节点 ui 和 vi 之间有一条边。

你必须在第一棵树和第二棵树中分别选一个节点,并用一条边连接它们。

请你返回添加边后得到的树中,最小直径 为多少。

一棵树的 直径 指的是树中任意两个节点之间的最长路径长度。

 

示例 1:

输入:edges1 = [[0,1],[0,2],[0,3]], edges2 = [[0,1]]

输出:3

解释:

将第一棵树中的节点 0 与第二棵树中的任意节点连接,得到一棵直径为 3 的树。

示例 2:

输入:edges1 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]], edges2 = [[0,1],[0,2],[0,3],[2,4],[2,5],[3,6],[2,7]]

输出:5

解释:

将第一棵树中的节点 0 和第二棵树中的节点 0 连接,可以得到一棵直径为 5 的树。

 

提示:

  • 1 <= n, m <= 105
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • edges1[i] = [ai, bi]
  • 0 <= ai, bi < n
  • edges2[i] = [ui, vi]
  • 0 <= ui, vi < m
  • 输入保证 edges1 和 edges2 分别表示一棵合法的树。
通过次数
3.5K
提交次数
10.2K
通过率
34.2%


相关企业

提示 1
Suppose that we connected node a in tree1 with node b in tree2. The diameter length of the resulting tree will be the largest of the following 3 values:
  1. The diameter of tree 1.
  2. The diameter of tree 2.
  3. The length of the longest path that starts at node a and that is completely within Tree 1 + The length of the longest path that starts at node b and that is completely within Tree 2 + 1.
The added one in the third value is due to the additional edge that we have added between trees 1 and 2.

提示 2
Values 1 and 2 are constant regardless of our choice of a and b. Therefore, we need to pick a and b in such a way that minimizes value 3.

提示 3
If we pick a and b optimally, they will be in the diameters of Tree 1 and Tree 2, respectively. Exactly which nodes of the diameter should we pick?

提示 4
a is the center of the diameter of tree 1, and b is the center of the diameter of tree 2.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
edges1 =
[[0,1],[0,2],[0,3]]
edges2 =
[[0,1]]
Source