8872번: 빌라봉

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


$O(n+m)$

트리에서 나머지 지점까지의 거리의 최댓값이 최소가 되는 지점을 중심이라 하고 그 값을 반지름이라 하자.
반지름이 최대인 트리의 중심에 나머지 트리의 중심을 이어주면 된다.

따라서 답은 다음 가능한 경우 중 최댓값이다.

1. 트리의 최대 지름
2. 최대 반지름 + 두번째 반지름 + L
3. 두번째 반지름 + 세번째 반지름 + L*2

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, l, d[MXN], ck[MXN], r;
vector<pair<int, int> > adj[MXN];
void f(int h) {
    ck[h] = 1;
    for (auto it : adj[h]) if (!ck[it.first]) {
        f(it.first);
        d[h] = max(d[h], d[it.first] + it.second);
    }
}
int g(int h, int pl) {
    int m1 = pl, m2 = 0, t = 2e9;
    ck[h] = 0;
    for (auto it : adj[h]) if (ck[it.first]) {
        m2 = max(m2, d[it.first] + it.second);
        if (m1 < m2) swap(m1, m2);
    }
    r = max(r, m1 + m2);
    for (auto it : adj[h]) if (ck[it.first]) t = min(t, g(it.first, (m1 == d[it.first] + it.second ? m2 : m1) + it.second));
    return min(m1, t);
}
int main() {
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    for (int i = 0; i < n; i++) if (!ck[i]) f(i);
    int m[3] = { -1000000000,-1000000000 };
    for (int i = 0; i < n; i++) if (ck[i]) {
        m[2] = max(m[2], g(i, 0));
        for (int j = 3; --j;) if (m[j] > m[j - 1]) swap(m[j], m[j - 1]);
    }
    printf("%d", max({ r,m[0] + m[1] + l,m[1] + m[2] + l * 2 }));
    return 0;
}