[백준] 12896 스크루지 민호

문제를 읽어보면 최대값은

각 정점에서 가장 먼 정점과의 거리 중 최소값이다

트리의 지름 공부할 때 배워둔

각 정점에서 가장 먼 거리를 구하면 된다 ㅎㅎ

유용하게 쓰이는 것 같다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 5;
vector<vector<int>> Graph;
bool check[MAXN];
int n, dist[MAXN], dist2[MAXN], far[MAXN];
 
void dist_dfs(int x) {
    check[x] = true;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (check[next])  continue;
        dist_dfs(next);
        if (dist[x] < dist[next] + 1) {
            dist2[x] = dist[x];
            dist[x] = dist[next] + 1;
        }
        else if (dist2[x] < dist[next] + 1) dist2[x] = dist[next] + 1;
    }
}
void far_dfs(int x, int parent_far) {
    check[x] = true;
    far[x] = max(dist[x], parent_far);
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (check[next]) continue;
        if (dist[x] == dist[next] + 1)    far_dfs(next, max(parent_far + 1, dist2[x] + 1));
        else far_dfs(next, max(parent_far + 1, dist[x] + 1));
    }
}
int main() {
    scanf(" %d", &n);
    Graph.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        a--; b--;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
    }
    dist_dfs(0);
    memset(check, 0, sizeof(check));
    far_dfs(0, 0); 
    int ans = 1e9;
    for (int i = 0; i < n; i++) ans = min(ans, far[i]);
    printf("%d\n", ans);
}