撰写定义:
一棵树的直径就是这棵树上存在的最长路径。
求法:
两次dfs或bfs。第一次任意选一个点进行dfs(bfs)找到离它最远的点，此点就是最长路的一个端点，再以此点进行dfs（bfs），找到离它最远的点，此点就是最长路的另一个端点，于是就找到了树的直径。
证明：
1 设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则
dis(u,T) >dis(u,s) 且 dis(u,T)>dis(u,t) 则最长路不是s-t了，与假设矛盾
2 设u不为s-t路径上的点
首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了
所以现在又有两种情况了：
1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)
2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，
则dis(s,X)+dis(u,T)-dis(u,X)>dis(s,X)+dis(X,u)+dis(u,T)>dis(s,X)+dis(X,t)=dis(s,t) 即dis(s,T)>dis(s,t)最长路不是s-t矛盾
代码：
/*树的直径是指树的最长简单路。求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；
原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了
所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度
*/
#include <bits/stdc++.h>
using namespace std;
#define INF 10000000000
vector <int > G[1000005];
vector<int > E[1000005];
bool vis[1000005];
int d[1000005];
void init() {
memset(vis, 0, sizeof(vis));
}
void dfs(int u) {
vis[u] = 1;
int size = G[u].size(); //与顶点u相连的点数
for (int i = 0; i<size; i++) { //对与顶点u相连的点数进行扫描
int v = G[u][i];
if (!vis[v]) {
d[v] = d[u] + E[u][i];
dfs(v);
}
}
}
int main() {
int n;
cin >> n;
int u, v, w;
for (int i = 0; i<n-1; i++) { //建立树过程
scanf("%d%d%d",&u,&v,&w);
G[u-1].push_back(v-1); //顶点两边都要记录
E[u-1].push_back(w);
G[v-1].push_back(u-1);
E[v-1].push_back(w);
}
init();
for (int i = 0; i<n; i++) d[i] = (i == 0?0:INF);
dfs(0);
int start = 0;
int max = -1;
for (int i = 0; i<n; i++) {
if (d[i] > max && d[i] != INF) {
max = d[i];
start = i;
}
}
init();
for (int i = 0; i<n; i++) d[i] = (i == start?0:INF);
dfs(start);
int ans = -1;
for (int i = 0; i<n; i++) {
if (d[i] > ans && d[i] != INF) {
ans = d[i];
}
}
//ans = 10*ans + ans*(ans+1)/2;
cout << ans << endl; //ans 即为直径
return 0;
}