1207. 大臣的旅费 - AcWing题库
很久以前，TT 王国空前繁荣。
为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，TT 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
JJ 是 TT 国重要大臣，他巡查于各大城市之间，体察民情。
所以，从一个城市马不停蹄地到另一个城市成了 JJ 最常做的事情。
他有一个钱袋，用于存放往来城市间的路费。
聪明的 JJ 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关。
具体来说，一段连续的旅途里，第 11 千米的花费为 1111，第 22 千米的花费为 1212，第 33 千米的花费为 1313，…，第 xx 千米的花费为 x+10x+10。
也就是说，如果一段旅途的总长度为 11 千米，则刚好需要花费 1111，如果一段旅途的总长度为 22 千米，则第 11 千米花费 1111，第 22 千米花费 1212，一共需要花费 11+12=2311+12=23。
JJ 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式
输入的第一行包含一个整数 nn，表示包括首都在内的 TT 王国的城市数。
城市从 11 开始依次编号，11 号城市为首都。
接下来 n−1n−1 行，描述 TT 国的高速路（TT 国的高速路一定是 n−1n−1 条）。
每行三个整数 Pi,Qi,DiPi,Qi,Di，表示城市 PiPi 和城市 QiQi 之间有一条双向高速路，长度为 DiDi 千米。
输出格式
输出一个整数，表示大臣 JJ 最多花费的路费是多少。
数据范围
1≤n≤1051≤n≤105,
1≤Pi,Qi≤n1≤Pi,Qi≤n,
1≤Di≤10001≤Di≤1000
输入样例：
5 1 2 2 1 3 1 2 4 5 2 5 4输出样例：
135
树的直径 - OI Wiki
#include <bits/stdc++.h> // 引入所有标准库，常用于竞赛编程，但在生产环境中不推荐使用
using namespace std; // 使用标准命名空间
using LL = long long; // 定义LL为long long类型，便于处理大整数
// 图的邻接表表示，每个pair包含一个连接节点和它们之间的边的长度
vector<vector<pair<LL, LL>>> graph;
LL ret = 0; // 用来存储找到的最长路径的长度
vector<bool> check; // 记录节点是否访问过，以避免重复访问
LL lastpos = 0; // 存储最长路径终点的位置，用于第二次DFS的起点
// 深度优先搜索函数，pos表示当前节点位置，path表示从起点到当前节点的路径长度
void dfs(LL pos, LL path) {
if (path > ret) lastpos = pos; // 如果当前路径长度超过已知的最长长度，则更新
ret = max(ret, path); // 更新最长路径长度
check[pos] = true; // 标记当前节点为已访问
for (auto& x : graph[pos]) { // 遍历当前节点的所有邻接节点
if(!check[x.first]) dfs(x.first, path + x.second); // 如果邻接节点未访问，递归调用DFS
}
check[pos] = false; // 回溯时取消当前节点的访问标记
}
int main() {
int n; cin >> n; // 输入节点数量
graph = vector<vector<pair<LL, LL>>>(n+1); // 初始化图的邻接表，节点编号从1到n
check.resize(n+1,false); // 初始化访问标记数组
for (LL i = 1; i < n; i++) { // 读入n-1条边信息，适用于树（无环连通图）
LL start, end, length;
cin >> start >> end >> length; // 输入每条边连接的两个节点及其长度
graph[start].push_back({end, length}); // 在邻接表中加入边
graph[end].push_back({start, length}); // 因为是无向图，所以两边都要加
}
dfs(1, 0); // 从节点1开始第一次DFS
dfs(lastpos, 0); // 从最远点开始第二次DFS以找到真正的树的直径
// 输出最长路径长度的平方加上21倍的最长路径长度，然后除以2的结果
cout << (ret * ret + 21 * ret) / 2;
}结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
