트리의 지름

https://www.acmicpc.net/problem/1967

//////////////////////////////////////////////////////////////////////////////
/* 
 _____                            ______                             _        
/  ___|                           | ___ \                           (_)       
\ `--.  _ __    __ _   ___   ___  | |_/ /  ___  _ __    __ _  _   _  _  _ __  
 `--. \| '_ \  / _` | / __| / _ \ |  __/  / _ \| '_ \  / _` || | | || || '_ \ 
/\__/ /| |_) || (_| || (__ |  __/ | |    |  __/| | | || (_| || |_| || || | | |
\____/ | .__/  \__,_| \___| \___| \_|     \___||_| |_| \__, | \__,_||_||_| |_|
       | |                                              __/ |                 
       |_|                                             |___/     
//////////////////////////////////////////////////////////////////////////////
 */
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

#define X first
#define Y second
#define int int64_t
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define Compress(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define OOB(x, y) ((x) < 0 || (x) >= n || (y) < 0 || (y) >= m)
#define IDX(v, x) (lower_bound(all(v), x) - (v).begin())
#define debug(x) cout << (#x) << ": " << (x) << '\n'
#define sf1(a) cin >> a
#define sf2(a, b) cin >> a >> b
#define sf3(a, b, c) cin >> a >> b >> c
#define sf4(a, b, c, d) cin >> a >> b >> c >> d
#define sf5(a, b, c, d, e) cin >> a >> b >> c >> d >> e
#define sf6(a, b, c, d, e, f) cin >> a >> b >> c >> d >> e >> f
#define pf1(a) cout << (a) << ' '
#define pf2(a, b) cout << (a) << ' ' << (b) << ' '
#define pf3(a, b, c) cout << (a) << ' ' << (b) << ' ' << (c) << ' '
#define pf4(a, b, c, d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' '
#define pf5(a, b, c, d, e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << ' '
#define pf6(a, b, c, d, e, f) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << ' ' << (f) << ' '
#define pf0l() cout << '\n';
#define pf1l(a) cout << (a) << '\n'
#define pf2l(a, b) cout << (a) << ' ' << (b) << '\n'
#define pf3l(a, b, c) cout << (a) << ' ' << (b) << ' ' << (c) << '\n'
#define pf4l(a, b, c, d) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << '\n'
#define pf5l(a, b, c, d, e) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << '\n'
#define pf6l(a, b, c, d, e, f) cout << (a) << ' ' << (b) << ' ' << (c) << ' ' << (d) << ' ' << (e) << ' ' << (f) << '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define pfvec(V)           \
for (auto const &t : V) \
pf1(t)
#define pfvecl(V)           \
for (auto const &t : V) \
pf1(t);             \
pf0l()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define Init(x, y) memset(x, y, sizeof(x));
#define EACH(x, a) for (auto& x: a)

using ll  = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using tii = tuple<int, int, int>;

using vi = vector<int>;
using vp = vector<pii>;
using vvi = vector<vi>;
using vvp = vector<vp>;
template <typename T>
using wector = vector<vector<T>>;
template <typename T>
using max_heap = priority_queue<T>;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> T max(vector<T> v) { return *max_element(all(v)); }

template<typename T>
void read(vector<T>& v){
EACH(i,v) sf1(i);
}

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int ddx[8] = {0, 0, 1, 1, 1, -1, -1, -1}, ddy[8] = {1, -1, 1, 0, -1, 1, 0, -1};
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const int INF = 1e9 + 7;

int n,mx,t;
vector<pii> adj[11111];
vector<bool> vist(11111);

void DFS(int cur,int len){
    if(len > mx){
        t = cur;
        mx = max(mx, len);
    }
    vist[cur] = 1;
    for(auto [dist, nxt] : adj[cur]){
        if(vist[nxt]) continue;
        DFS(nxt, dist + len);
    }
}

int32_t main(){
    fastio;
    sf1(n);
    rep(i, 1, n){
        int a,b,c; sf3(a, b, c);
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    DFS(1, 0);
    fill(all(vist), 0);
    mx = 0;
    DFS(t, 0);
    pf1l(mx);
}

아무 정점이나 잡고 DFS를 1번 돌려서 가장 먼 정점을 찾자. 이 정점을 t라고 한다.
t인 정점에서 mx(가장 긴 거리)의 값고 vist배열을 초기화 한 후 t정점을 시작으로 가장 먼 거리를 찾는다.
이 거리가 가장 긴 트리의 지름이 된다.