/*
C++米哈游编程题第2题：计算给定树的最大深度不超过 k 的路径数量
原来的代码是牛客的一位哈工大计算机大佬的python版本，
这里用chatGPT改为C++版本。
以下是chatGPT的回答
*/
/*
这段代码实现了一个树状结构的深度优先搜索（DFS），
用于计算从树的根节点开始，最大深度不超过k的路径数量。
让我解释一下它的主要部分：
首先，从标准输入中读取两个整数 n 和 k，其中 n 表示树的节点数，k 表示最大深度。
接下来，通过循环读取 n-1 条边的信息，每条边连接两个节点。这些边构建了树的结构。
使用一个名为 G 的向量数组，其中每个元素 G[i] 表示节点 i 的子节点列表。
这个向量数组用于表示树的结构。
定义了一个递归函数 dfs，它接受三个参数：当前节点 cur、当前深度 depth 和父节点 parent。
这个函数的目标是计算以当前节点为根的子树中，最大深度不超过 k 的路径数量。
在 dfs 函数中，首先检查当前深度是否超过了 k，
如果是，则返回 0，表示不计算该子树的路径数量。
如果当前深度没有超过 k，就初始化 ans 为 1，表示至少有一条路径（即当前节点本身）。
接下来，检查当前节点是否有多于一个子节点或者是根节点（parent 为 -1）。
如果是这样，就遍历当前节点的所有子节点，递归调用 dfs 函数，并将结果累加到 ans 中。
如果当前节点没有多于一个子节点，那么只有一种情况会增加路径数量，即当前深度不超过 k。
因此，将 k 减去当前深度，并将结果与 0 比较，然后将较大值累加到 ans 中。
最后，主函数调用 dfs 函数，从根节点开始计算路径数量，并将结果输出到标准输出。
总之，这段代码的目标是计算给定树的最大深度不超过 k 的路径数量。
*/
#include <iostream> // 引入输入/输出流库
#include <vector> // 引入向量容器库
using namespace std; // 使用C++标准库的命名空间，以便可以直接使用标准库的函数和类
const int MAXN = 1000000; // 声明一个常量，表示最大节点数。根据需要调整此值。
int n, k; // 声明两个整数变量，用于存储输入的树的节点数和最大深度
vector<int> G[MAXN]; // 声明一个向量数组，用于表示树的结构。每个元素 G[i] 是一个整数向量，表示节点 i 的子节点列表
int dfs(int cur, int depth, int parent) { // 定义递归函数 dfs，用于计算从当前节点开始，最大深度不超过 k 的路径数量
if (depth > k) { // 检查当前深度是否超过 k，如果是，返回 0 表示不计算该子树的路径数量
return 0;
}
int ans = 1; // 初始化 ans 为 1，表示至少有一条路径（即当前节点本身）
if (G[cur].size() > 1 || parent == -1) { // 检查当前节点是否有多于一个子节点或者是根节点。如果是这样，进入循环。
for (int i = 0; i < G[cur].size(); ++i) { // 遍历当前节点的所有子节点
int child = G[cur][i]; // 获取当前子节点的索引
if (child != parent) { // 检查当前子节点是否等于父节点。如果不等于，说明当前子节点是有效的。
ans += dfs(child, depth + 1, cur); // 递归调用 dfs 函数，将结果累加到 ans 中
}
}
}
else { // 如果当前节点没有多于一个子节点，进入 else 分支
ans += max(0, k - depth); // 将 0 和 k - depth 中的较大值累加到 ans 中。这表示只有一种情况会增加路径数量，即当前深度不超过 k。
}
return ans; // 返回路径数量
}
int main() { // 定义程序的主函数
ios_base::sync_with_stdio(false); // 提高输入操作的性能
cin.tie(nullptr);
cin >> n >> k; // 从标准输入中读取树的节点数 n 和最大深度 k
for (int i = 0; i < n - 1; ++i) { // 循环读取 n-1 条边的信息
int u, v; // 声明两个整数变量 u 和 v，用于存储边的两个节点
cin >> u >> v; // 从标准输入中读取边的信息
G[u - 1].push_back(v - 1); // 将边信息添加到 G 中，构建树的结构
G[v - 1].push_back(u - 1);
}
int result = dfs(0, 0, -1); // 调用 dfs 函数，从根节点开始计算路径数量，并将结果存储在 result 变量中
cout << result << endl; // 将计算得到的路径数量输出到标准输出
return 0; // 返回程序的退出状态码
}
查看22道真题和解析
