1.从任意一个点r出发，求距离他最远的点s。点s肯定是树的直径上的一个端点
2.从点s出发，求距离点s最远的点t。s和t就是最远的两个点，即树的直径
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std ; const int N = 1e5 +10 ; int n ; struct edge{ int to , w ; }; vector<edge> e[N] ; int dist[N] ; //这是逐层往下进行搜索的，保证能搜索到每一个点，每到一个新的点就进行距离的增加 void dfs(int u ,int fa , int d){//dfs找到距离u的最远的点 dist[u] = d; for(int i = 0 ; i < e[u].size() ; i ++){ int to = e[u][i].to , w = e[u][i].w; if(to != fa){ dfs(to,u,d+w) ; } } } int main(){ cin >> n ; for(int i = 1 ; i < n ; i ++) { int a , b , c; cin >> a >> b >> c ; e[a].push_back({b,c}) ; e[b].push_back({a,c}) ; } dfs(1,-1,0) ;//随便挑一个点找到距离最远的点，这个点的就是直径的一个端点 int root = 1 ; int res = 0 ; for(int i = 1 ; i <= n ; i ++){//遍历找到端点 if(dist[i] > res) { res = dist[i] ; root = i ; } } dfs(root,-1,0) ;//从这一个端点进行遍历，一定能找到最远的一个点，这个点就是直径的另一个端点 res = 1 ; for(int i = 1 ; i<= n ; i++){//找到最远距离，即直径 res = max(res , dist[i]) ; } int ans = 0 ; for(int i = 1 ; i <= res ;i ++){ ans += 10 + i ; } cout << ans << endl; }
