‹ 上一题 下一题 ›

g6-07590. 一次后序求直径·为什么正确 未做

1000 ms 256 MB 测试点 ? 自拟题知识点题GESP-66级·树形 DP 入门客观题单选

一次后序 DFS 就能求直径:每个点维护「向下最长链」,并在每个点用「最长 + 次长」更新答案。这个做法正确的原因是( )。

  • A. 直径一定经过根
  • B. 因为后序保证孩子先算完
  • C. 因为用了两次 DFS
  • D. 任一条最长路径都有唯一的「最高点」,在 处它恰好由两条来自不同孩子的链拼成 —— 枚举每个点的「最长 + 次长」就覆盖了所有候选
未选择
输入
输出

            
答案