‹ 上一题 下一题 ›

g6-07538. 答案位置·为什么不能只输出 未做

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

一位同学这样求直径(最长简单路径的边数):

int dfs(int u) {
    int h = 0;
    for (int v : ch[u]) h = max(h, dfs(v) + 1);
    return h;              // 只向上返回「最大深度」
}

树:1-2、2-3、3-4、3-5、2-6、6-7、6-8(1 号是根)。

主函数 cout << dfs(1) 输出 3,但真正的直径是 4。原因是( )。

  • A. 树的直径一定经过根,程序却只算了根到最深叶子的距离
  • B. 最长路径可能完全落在子树内部(如 5-3-2-6-7),所以答案要在「合并两条孩子链」处随时更新,而不是取
  • C. 程序缺少父参数 fa,会沿着边往回走、重复访问
  • D. 程序没开 long long,深链上的求和会溢出
未选择
输入
输出

            
答案