牛客25606题解：DFS计算树结构最优解

一、问题理解

牛客25606题要求我们计算树结构中的最优解，这个问题可以转化为寻找树的最长路径（直径）问题。通过DFS遍历树结构，我们可以高效地解决这类典型的图论问题。

二、算法核心思想

1. ‌树结构表示‌：使用邻接表存储树

2. ‌DFS遍历‌：深度优先搜索计算最大深度

3. ‌公式推导‌：利用数学公式2*(N-1)-max_depth得出结果

三、完整代码实现（带注释）

C++

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> graph;
vector<bool> visited;
int max_depth = 0;

void dfs(int node, int depth) {
    visited[node] = true;
    max_depth = max(max_depth, depth);
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, depth + 1);
        }
    }
}

int main() {
    int N;
    cin >> N;
    graph.resize(N + 1);
    visited.resize(N + 1, false);
    
    for (int i = 0; i < N - 1; ++i) {
        int X, Y;
        cin >> X >> Y;
        graph[X].push_back(Y);
        graph[Y].push_back(X);
    }
    
    dfs(1, 0);
    cout << 2 * (N - 1) - max_depth << endl;
    return 0;
}

关键知识点

1. ‌邻接表‌：高效存储树结构的数据结构

2. ‌DFS算法‌：深度优先搜索的基本原理

3. ‌递归实现‌：DFS的递归实现方式

4. ‌树的性质‌：树是无向无环连通图

来源：牛客题解