第一部分：背景知识讲解

1. 三国鼎立与蜀道难 (The Three Kingdoms)

三国时期，蜀汉占据益州（今四川），四周崇山峻岭，道路崎岖。诸葛亮为了北伐中原，修筑了连绵的栈道和烽火台。

2. 树形防御网络

由于地形限制，这些烽火台之间的连接路径是唯一的，没有回路。如果把烽火台看作节点，山路看作边，这就构成了一棵树 (Tree)。

3. 算法模型：树的直径 (Tree Diameter)

为了评估防御体系的最大预警时间，我们需要找到两个距离最远的烽火台。 在图论中，树上最远的两个节点之间的距离被称为树的直径。

• 求解方法：两次搜索法（Two-pass DFS/BFS）。
  1. 从任意一点出发，找到距离它最远的点 $U$。
  2. 从 $U$ 出发，找到距离它最远的点 $V$。
  3. $U$ 到 $V$ 的距离即为直径。

第二部分：题目内容

题目名称：蜀汉的烽火 (The Beacons of Shu Han)

题目描述

蜀汉丞相诸葛亮在汉中建立了一套烽火防御体系。 共有 $N$ 座烽火台，编号为 $1$ 到 $N$。 这些烽火台之间通过 $N-1$ 条双向山路相连，保证任意两座烽火台都可以互相到达（即构成一棵树）。 第 $i$ 条山路连接了烽火台 $u_i$ 和 $v_i$，其长度（通讯耗时）为 $w_i$。

为了测试烽火传递的极限延迟，诸葛亮需要找出两座烽火台，使得它们之间的距离（路径长度之和）最大。 请你编写程序，计算出这个最大距离是多少。

输入格式

第一行包含一个正整数 $N$，表示烽火台的数量。

接下来 $N-1$ 行，每行包含三个正整数 $u, v, w$，表示烽火台 $u$ 和 $v$ 之间有一条长度为 $w$ 的道路。

输出格式

输出一行一个整数，表示树的直径（最大距离）。

输入输出样例 #1

输入：

4
1 2 10
2 3 20
2 4 5

输出：

30

样例 #1 解释： 树的结构如下：

• $1$ 与 $2$ 相连，距离 $10$
• $2$ 与 $3$ 相连，距离 $20$
• $2$ 与 $4$ 相连，距离 $5$ 最远路径是 $1 \to 2 \to 3$，总长度 $10 + 20 = 30$。 （对比：$3 \to 2 \to 4$ 长度为 $25$；$1 \to 2 \to 4$ 长度为 $15$）。

输入输出样例 #2

输入：

6
1 2 5
2 3 10
2 4 8
1 5 6
5 6 20

输出：

41

样例 #2 解释： 最长路径为 $6 \to 5 \to 1 \to 2 \to 3$。 距离计算：$20 + 6 + 5 + 10 = 41$。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• $1 \le w_i \le 1000$
• 保证输入构成一棵树。

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

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)

见题解