第三部分：题目分析与标准代码

1. 算法分析

• 暴力法：对每个点做一次 BFS/DFS 求最远距离，复杂度 $O(N^2)$。$N=10^5$ 时会超时。
• 两次 DFS 法：
  • 第一次 DFS：从节点 1 出发，找到最远节点 $U$。
  • 第二次 DFS：从节点 $U$ 出发，找到最远节点 $V$。
  • $dist(U, V)$ 即为答案。
  • 时间复杂度 $O(N)$，空间复杂度 $O(N)$。

2. 标准代码 (C++14)

/**
 * 题目：蜀汉的烽火
 * 难度：GESP 6级
 * 算法：树的直径 (两次 DFS)
 */

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

const int MAXN = 100005;

// 邻接表结构体
struct Edge {
    int to;
    int w;
};
vector<Edge> adj[MAXN];

// 记录最远节点及其距离
int farthest_node;
long long max_dist;

// DFS 遍历
// u: 当前节点, fa: 父节点(防止走回头路), d: 当前累积距离
void dfs(int u, int fa, long long d) {
    // 如果当前距离比记录的最大距离还大，更新
    if (d > max_dist) {
        max_dist = d;
        farthest_node = u;
    }

    // 遍历所有相邻边
    for (auto& e : adj[u]) {
        if (e.to != fa) {
            dfs(e.to, u, d + e.w);
        }
    }
}

int main() {
    fast_io();

    int N;
    if (!(cin >> N)) return 0;

    // 特判 N=1 的情况
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }

    // 读入树
    for (int i = 0; i < N - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // 第一遍 DFS：从任意点(例如1)出发，找到最远点 U
    max_dist = -1;
    dfs(1, 0, 0);
    int start_node = farthest_node;

    // 第二遍 DFS：从 U 出发，找到最远点 V
    max_dist = -1;
    dfs(start_node, 0, 0);

    // 此时 max_dist 即为直径
    cout << max_dist << endl;

    return 0;
}

第四部分：数据生成器

这是一个功能完备的数据生成器，生成的测试点涵盖了链状、星状、扫把星等能卡掉错误算法的特殊树形。

/**
 * GESP 6级 [蜀汉的烽火] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
const int MAXN_SOLVE = 100005;
struct EdgeS { int to; int w; };
vector<EdgeS> adj_s[MAXN_SOLVE];
long long max_d_s;
int far_node_s;

void dfs_s(int u, int fa, long long d) {
    if (d > max_d_s) {
        max_d_s = d;
        far_node_s = u;
    }
    for (auto& e : adj_s[u]) {
        if (e.to != fa) dfs_s(e.to, u, d + e.w);
    }
}

long long solve(int N, const vector<tuple<int, int, int>>& edges) {
    if (N == 1) return 0;
    for (int i = 1; i <= N; i++) adj_s[i].clear();
    for (const auto& e : edges) {
        adj_s[get<0>(e)].push_back({get<1>(e), get<2>(e)});
        adj_s[get<1>(e)].push_back({get<0>(e), get<2>(e)});
    }

    // 第一次搜索
    max_d_s = -1;
    dfs_s(1, 0, 0);
    int start = far_node_s;

    // 第二次搜索
    max_d_s = -1;
    dfs_s(start, 0, 0);
    
    return max_d_s;
}

// 辅助函数
int randRange(int min, int max) {
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N;
        vector<tuple<int, int, int>> edges;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 4;
            edges = {{1,2,10}, {2,3,20}, {2,4,5}};
        }
        else if (i == 2) {
            // 样例2
            N = 6;
            edges = {{1,2,5}, {2,3,10}, {2,4,8}, {1,5,6}, {5,6,20}};
        }
        else if (i == 3) {
            // 最小树 (2个点)
            N = 2;
            edges = {{1, 2, 100}};
        }
        else if (i == 4) {
            // 链状树 (直径 = 所有边权和)
            N = 100;
            for(int k=1; k<N; k++) edges.emplace_back(k, k+1, randRange(1, 10));
        }
        else if (i == 5) {
            // 菊花图 (直径 = 最大的两个边权之和)
            N = 100;
            for(int k=2; k<=N; k++) edges.emplace_back(1, k, randRange(10, 1000));
        }
        else if (i == 6) {
            // 扫把星 (一条长链 + 末端发散)
            // 这种结构容易卡掉只从度数为1的点开始搜的错误贪心
            N = 100;
            // 1-50 是链
            for(int k=1; k<50; k++) edges.emplace_back(k, k+1, 100); 
            // 50 连接 51-100
            for(int k=51; k<=N; k++) edges.emplace_back(50, k, 1); 
        }
        else if (i == 7) {
            // 毛毛虫树 (一条主干，主干上挂叶子)
            N = 1000;
            int len = 500;
            for(int k=1; k<len; k++) edges.emplace_back(k, k+1, randRange(10, 20));
            for(int k=len+1; k<=N; k++) {
                int p = randRange(1, len);
                edges.emplace_back(p, k, randRange(1, 5));
            }
        }
        else {
            // 大规模随机树 (N=10^5)
            N = 100000;
            // 随机树生成：节点 i 挂在 1~i-1 中某个点下面
            for(int k=2; k<=N; k++) {
                // max(1, k-1000) 让树倾向于长条形，避免太扁
                int p = randRange(max(1, k-1000), k-1); 
                edges.emplace_back(p, k, randRange(1, 1000));
            }
        }

        // 写入输入
        fin << N << "\n";
        for (const auto& e : edges) {
            fin << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << "\n";
        }

        // 写入输出
        fout << solve(N, edges) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}