BOJ)5038 Flight Planning

문제: icpc.me/5038

트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다.

N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다.

그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까?

바로 트리의 반지름을 이용하면 된다.

트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다.

이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 

트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다.

따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
vector<pair<int, int>> edge, f;
vector<int> dist, visited, visited2, back, ra;
int n, x, y, r, u, v, rr, idx;
vector<vector<int>> vt;
void dfs(int here, int dis) {
    visited[here] = 1;
    dist[here] = dis;
    if (r <= dist[here]) {
        r = dist[here];
        u = here;
    }
    for (auto next : vt[here]) {
        if (visited[next])continue;
        dfs(next, dis + 1);
    }
}
void dfs2(int here, int dis) {
    visited2[here] = 1;
    dist[here] = dis;
    if (r < dist[here]) {
        r = dist[here];
        v = here;
    }
    for (auto next : vt[here]) {
        if (visited2[next])continue;
        dfs2(next, dis + 1);
        back[next] = here;
    }
}
pair<int, int> solve(int e) {
    vt.clear();
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        if (i == e)continue;
        vt[edge[i].first].push_back(edge[i].second);
        vt[edge[i].second].push_back(edge[i].first);
    }
    dist.assign(n + 1, INF);
    visited.assign(n + 1, 0);
    visited2.assign(n + 1, 0);
    back.assign(n + 1, 0);
    f.clear();
    ra.clear();
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i])continue;
        r = 0;
        v = i;
        dfs(i, 0);
        r = 0;
        back[u] = 0;
        dfs2(u, 0);
        f.push_back({ v,r });
        res = max(r, res);
    }
    int xx = -1, yy;
    for (int i = 0; i < 2; i++) {
        pair<int, int> next = f[i];
        int it = next.first;
        int g = INF;
        while (it) {
            int rad = max(dist[it], next.second - dist[it]);
            if (rad < g) {
                g = rad;
                if (!i)
                    xx = it;
                else
                    yy = it;
            }
            it = back[it];
        }
        ra.push_back(g);
    }
    int sol = max(max(f[0].second, f[1].second), ra[0] + ra[1] + 1);
    if (rr > sol) {
        rr = sol;
        idx = e;
    }
    return{ xx,yy };
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d", &x, &y);
        edge.push_back({ x,y });
    }
    rr = INF;
    for (int i = 0; i < n - 1; i++)
        solve(i);
    printf("%d\n", rr);
    pair<int, int> s = solve(idx);
    printf("%d %d\n", edge[idx].first, edge[idx].second);
    printf("%d %d\n", s.first, s.second);
    return 0;
}