一位同学这样求直径(最长简单路径的边数):
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,深链上的求和会溢出