[BOJ] 1967번: 트리의 지름

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

트리의 지름이란 트리에서 노드 간 가장 긴 길이를 의미한다. 

DFS를 아무 점에서 시작해서 가장 긴 부분의 위치를 찾는다. 그리고 그 위치에서 DFS를 돌려 가장 긴 부분을 찾는다. 그래서 나온 길이가 트리의 지름이 된다.

#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> pii;
int n, res, idx;
vector<pii> v[10001];
bool visited[10001];

void DFS(int d, int h)
{
    visited[h] = true;
    if (d > res)
        res = d, idx = h;
    for (auto &i : v[h])
    {
        if (!visited[i.first])
        {
            DFS(i.second + d, i.first);
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0, f, t, w; i < n - 1; ++i)
    {
        scanf("%d %d %d", &f, &t, &w);
        v[f].push_back({t, w});
        v[t].push_back({f, w});
    }
    DFS(0, 1);
    fill(visited, visited + n + 1, 0);
    DFS(0, idx);
    printf("%d\n", res);
    return 0;
}