lanqiao OJ 207 大臣的旅费(两次dfs)

#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; 
}