백준 1167 트리의 지름

모르면 풀기 어려운 문제다. 임의의 정점에서 최대 거리를 갖는 정점을 찾은 뒤 그 정점에서 다시 최대 거리를 갖는 정점까지의 거리가 트리의 지름이다. 이에 대한 증명은 여기 클릭.
어쨌든 아이디어를 안 이상 구현은 어렵지 않은 문제였다.

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int nowDist, maxDist, farNode;
void dfs(int n, vector<vector<pii>>& g, vector<int>& v) {
    for (int i = 0; i < g[n].size(); ++i) {
        int next = g[n][i].first;
        int cost = g[n][i].second;
        if (v[next]) continue;
        nowDist += cost;
        v[next] = 1;
        if (maxDist < nowDist) {
            maxDist = nowDist;
            farNode = next;
        }
        dfs(next, g, v);
        nowDist -= cost;
        v[next] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<vector<pii>> graph(n+1);
    vector<int> vis(n+1);
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        while (true) {
            int b;
            cin >> b;
            if (b == -1) break;
            int c;
            cin >> c;
            graph[a].push_back({b, c});
        }
    }
    vis[1] = 1;
    dfs(1, graph, vis);
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    maxDist = 0;
    vis[farNode] = 1;
    dfs(farNode, graph, vis);
    cout << maxDist;
}