[1167] 트리의 지름

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

1167번: 트리의 지름

<문제>

아무 노드를 하나 잡고 거리가 가장 먼 노드가 트리의 지름을 이루는 첫 번째 노드이고,

그 노드에서 가장 먼 노드가 트리의 지름을 이루는 두 번째 노드다.

증명도 직관적이고, typical한 유형인 것 같지만, dfs와 트리의 정의만 아는 상태에서 떠올리기엔 만만찮다. 

 

<소스코드>

#include <bits/stdc++.h>

using namespace std;

using pi = pair<int, int>;

vector<pi> adj[100001];

int n, ansIdx, ans;

bool vst[100001];

void f(int cur, int cost) {

    if (ans < cost) {

        ans = cost;

        ansIdx = cur;

    }

    for (auto& nxt : adj[cur]) {

        if (vst[nxt.first] == false) {

            vst[nxt.first] = true;

            f(nxt.first, cost + nxt.second);

        }

    }

}

int main(void) {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cin >> n;

    int i, j;

    for (i = 0; i < n; i++) {

        int idx;

        cin >> idx;

        while (1) {

            int A, B;

            cin >> A;

            if (A == -1) break;

            cin >> B;

            adj[idx].push_back({A, B});

            adj[A].push_back({idx, B});

        }

    }

    vst[1] = true;

    f(1, 0);

    memset(vst, 0, sizeof(vst));

    ans = 0;

    vst[ansIdx] = true;

    f(ansIdx, 0);

    cout << ans;

    return 0;

}