树形结构贪心算法解析：小Q的棋盘问题

1. 题目背景与需求分析

P3698 [CQOI2017] 小Q的棋盘是信息学奥林匹克竞赛（信奥）中的一道经典题目，考察选手对树形结构和贪心算法的掌握程度。题目描述小Q在一个n个节点的树形棋盘上行走，从根节点出发，最多走v步，问最多能经过多少个不同的节点。

这道题的核心在于理解树形结构的遍历特性。与线性结构不同，树形结构中节点之间存在父子关系，且没有环路。在实际编程竞赛中，这类问题通常需要将树形结构转化为可操作的数据模型，并设计高效的遍历策略。

注意：题目中的"步"指的是沿着树边移动的次数，每移动一条边算作一步。这与常规棋盘问题中的步数概念有所不同，需要特别注意。

2. 数据结构设计与输入处理

2.1 树的表示方法

在C++中，我们通常使用邻接表来表示树结构。对于每个节点，存储其相邻的子节点。这种表示方法既节省空间又便于遍历：

cpp复制const int MAXN = 105;
vector<int> tree[MAXN];

2.2 输入处理细节

题目输入首先给出两个整数n和v，分别表示树的节点数和最大步数。接着是n-1行，每行两个整数a和b，表示节点a和b之间有一条边。完整的输入处理代码如下：

cpp复制int n, v;
cin >> n >> v;
for (int i = 1; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    tree[a].push_back(b);
    tree[b].push_back(a);
}

提示：在实际竞赛中，建议总是检查输入数据的范围。虽然本题保证n≤100，但养成检查的习惯有助于避免其他题目中的边界错误。

3. 算法设计与实现

3.1 基本思路分析

这道题的关键观察点是：在树形结构中，要访问尽可能多的节点，应该优先走最长的分支。具体策略如下：

1. 首先找到从根节点出发的最长路径（深度最大的路径）
2. 如果步数足够走完这条路径并返回，那么可以访问所有节点
3. 如果步数不足，则优先走最长路径，剩余步数用于访问其他分支

3.2 深度优先搜索实现

我们需要两次DFS遍历：第一次计算每个节点的深度，第二次确定最长路径：

cpp复制int depth[