1167번: 트리의 지름

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


$O(n)$

http://codedoc.tistory.com/240

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, r;
vector<pair<int, int> > adj[100001];
int f(int h, int p) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) if (it.first^p) {
        m2 = max(m2, f(it.first, h) + it.second);
        if (m1 < m2) swap(m1, m2);
    }
    r = max(r, m1 + m2);
    return m1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, a, b, c; i <= n; i++) {
        scanf("%d", &a);
        while (scanf("%d", &b), b^-1) {
            scanf("%d", &c);
            adj[a].push_back({ b,c });
        }
    }
    f(1, 0);
    printf("%d", r);
    return 0;
}