C C++ 题解LeetCode2360图中的最长环示例

让我们详细讲解一下“C C++ 题解LeetCode2360图中的最长环示例”的完整攻略。

题目描述

题目传送门：LeetCode2360图中的最长环

题目描述：

给你一棵有n个节点的有根树，节点从0~n-1编号，树的根节点为0.

叶节点是指没有直接连接任何下一级节点的节点。本题中，树的节点从1到n编号, 而非从0到n-1编号.

节点 i 的父亲是 father[i]。一个节点的直接子节点是该节点连接的所有节点中编号最小的那些。例如，在图中的树中，节点 1 连接着节点 2 和节点 3 且节点 2 是节点 1 的子节点，节点 3 是节点 1 的另一个直接子节点。该树经过修改变成了一棵普通的无根树。你需要重新连接树边，以得到一棵直径最大的树。直径是树上最长路径的长度。用所需修改的边的个数来返回该长度。

题目分析

在题目中，我们需要把一个有根树转化为无根树，然后求出该无根树的直径，再根据需要修改的边数返回最长的直径长度。

先看怎样将一个有根树转化为无根树。我们可以让树中的任意一个节点作为根节点，以其他节点为根节点建立子树。但是，本题中我们并不知道那个节点才是原来的根节点。因此，我们需要枚举所有的节点作为根节点，以该节点为根节点建立子树并求出该子树的最长直径。最终所有的直径长度中的最大值即为所求。

无根树的直径可以用两次dfs求出，详细的求解过程可以参见我的博客：无根树的直径

接下来，我们再看怎样计算其中添加的边数。

我们发现，在有根树中，父节点到子节点的边是确定的。因此，每当我们枚举一个节点作为根节点并对树进行转化时，会造成一部分父节点到子节点的边的改变，不同姿势转换成的无根树造成的改变不同，我们需要对这些结果进行分析。

我们采用dfs从一个虚拟的根节点 root 开始遍历整个无根树，记录每个节点到虚拟根节点的距离，并维护一条最长路径，路径上的两个节点即为无根树的直径的两个端点。如果某个节点的两个子节点的距离和大于现有的最长路径长度，则更新最长路径。记录这个最长路径长度 later。

要想得出我们需要添加的边数 diff，先计算出无根树之前的最长直径长度 former。

diff = later - former。

最后，我们就可以得到这道题的完整解法了。

一条示例说明

以示例图为例，具体思路如下：

1. 先将节点0作为根节点, 枚举所有节点, 以该节点为根建立无根树, 并计算该无根树的直径, 该部分的添加的边数为3.
2. 然后将节点1作为根节点, 输入的树在以节点1为根的树形结构中的样子为:

   1(1)
  /     \
2(2)    3(4)

计算该树的时候需要修改2到4的路径，因此 diff = 1。最长直径为2。因此我们最重终态的答案应该为5 + 2 = 7

1. 最后再枚举2和3各一次即可。

不难发现，我们需要维护两个比较重要的变量：later 和 former。 下一个示例同理。

另一条示例说明

现在看练习题目传送门：第 113 周周赛 第二题

给出的树形结构为：

   3(1)
  /     \
2(2)    0(3)
   \     
    1(4)

初始无根树：

   3(1)
  /     \
2(2)    0(3)
   \     
    1(4)

以 3 作为根：

   3(1)
  /     \
2(2)    0(3)
   \     
    1(4)

该部分的添加边数为1，最长路径为1。

以 2 作为根：

       2(1)
      /   \
    3(2)  1(4)
      \     
       0(3)

该部分的添加边数为1，最长路径为3。

以 0 作为根：

   0(1)
  /     \
3(2)    2(3)
   \     
    1(4)

该部分的添加边数为1，最长路径为3。

以上两例都说明了这个题的思路，对于这些奇怪的示例可以用调试模式查看获得更好的体验。

代码实现

参考代码如下：