警示后人(如果你WA#12)(附hack数据)
  • 板块P10406 Company
  • 楼主Zhenghw
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/4 20:58
  • 上次更新2024/5/4 22:59:22
查看原帖
警示后人(如果你WA#12)(附hack数据)
1201196
Zhenghw楼主2024/5/4 20:58

计算的不是树的直径,而是最远的两个叶子节点!!! 如果你直接计算树的直径,那么如果这棵树只有一个叶子节点,算出来的直径就是根节点到最远的叶子结点的距离(这是不正确的)

解决方案: 1.在进行dfs时进行特判如果该节点的度为1,且不为根节点,也就是不为1号节点,这时才更新最长路。 2.假如我们使用maxx变量来记录树的高度减去最远的两个叶子节点的距离,那么它是可以为负数的,因此开始时要将其设为极小值!!!

为了更直观一些,下面给出一组hack数据:

Input:
2
4 1 2 3
4 1 2 3
4 4

Output:
4
2024/5/4 20:58
加载中...