1967번: 트리의 지름

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


1. 트리 DP

$O(n)$

rooted tree를 만든다.
x번 노드가 루트인 서브트리 내에서 트리의 지름 다음 중 최댓값이다.
1. x번 노드의 자식이 루트인 서브트리 내에서 트리의 지름
2. 리프 노드에서 x번 노드까지의 두 최장경로 길이 합

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 1e4;
vector<pair<int, int> > adj[MAX_N + 1];
int n, res;
int dfs(int h) {
    int r1 = 0, r2 = 0;
    for (auto it : adj[h]) {
        r2 = max(r2, it.second + dfs(it.first));
        if (r1 < r2) swap(r1, r2);
    }
    res = max(res, r1 + r2);
    return r1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y, z; i < n - 1; i++) {
        scanf("%d %d %d", &x, &y, &z);
        adj[x].push_back({ y,z });
    }
    dfs(1);
    printf("%d", res);
    return 0;
}

2. DFS 두 번

$O(n)$

아무 정점 하나를 시작점으로 잡아 그 지점으로부터 가장 먼 지점을 찾는다.
이 지점은 트리의 지름에서 양 끝 지점 중 하나가 된다.
마찬가지로 이 지점을 시작점으로 잡아 그 지점으로부터 가장 먼 지점을 찾는다.
이 지점은 지름의 양 끝 지점 중 나머지 하나가 된다.

증명은
http://blog.myungwoo.kr/112

#include<cstdio>
#include<vector>
using namespace std;
int res, n, idx;
vector<pair<int, int> > adj[10001];
void f(int h, int p, int d) {
        if (d > res) res = d, idx = h;
        for (auto it : adj[h]) if (it.first^p) f(it.first, h, d + it.second);
}
int main() {
        scanf("%d", &n);
        for (int i = 0, x, y, z; i < n - 1; i++) {
                scanf("%d%d%d", &x, &y, &z);
                adj[x].push_back({ y,z });
                adj[y].push_back({ x,z });
        }
        f(1, 0, 0);
        f(idx, 0, 0);
        printf("%d", res);
        return 0;
}