2970번: 두더지

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


$O(n)$

먼저, 트리의 지름(트리 상에서 가장 먼 두 정점의 경로)을 구한다.
지름의 끝 정점을 s1, s2라 하자.
s1과 s2를 잇는 경로상의 한 간선을 지워야 한다. 그러지 않는다면, 지름의 값이 가장 먼 두 정점의 거리가 될 것이기 때문이다.
간선을 하나 지웠다고 해보자. 문제는 s1을 포함하는 트리의 지름과 s2를 포함하는 트리의 지름에 의해 답이 결정된다.
s1-a1-a2-a3- ... - an-s2 (ai는 가지를 가질 수도 있다.) 모양에서
s1 ~ ai, ai~s2 트리마다의 지름을 구해야 한다.
이는 s1,s2를 시작 정점으로 하는 dfs 탐색을 이용해 해결할 수 있다.
이에 대해 간략하게 말하면 탐색에서 자신을 끝으로 하는 사슬의 최대 길이와 자식들의 지름을 가지고 갱신시키면 된다.
(본 블로그 내의 트리의 지름 1번 풀이를 참고하자. http://codedoc.tistory.com/240)
a(i-1) 과 ai를 끊었을 때의 최소 거리는 다음 세 값 중 최댓값이다.
1. s1~a(i-1) 상의 지름
2. ai~s2 상의 지름
3. s1~a(i-1) 반지름 + ai~s2 반지름 + 1
최댓값이 가장 작을 때가 답이다.
자를 곳을 결정했다면 그 간선을 제거하고 나눠진 트리에서 각각 중심점을 찾고 이으면 된다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 3e5;
vector<int> adj[MAX_N + 1];
int n, maxi, t, ck[MAX_N + 1];
int vis[MAX_N], vck;
void dfs1(int h, int p, int dep, int v) {
    if (dep > maxi) maxi = dep, t = h;
    ck[h] = 1;
    if (v != -1 && !vck) vis[dep] = h;
    if (h == v) vck = 1;
    for (auto it : adj[h])
        if (!ck[it]) dfs1(it, h, dep + 1, v);
    ck[h] = 0;
}
int l[2][MAX_N + 1];
int dfs2(int h, int p, int idx) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) {
        if (it == p) continue;
        m2 = max(m2, dfs2(it, h, idx) + 1);
        if (m1 < m2) swap(m1, m2);
        l[idx][h] = max(l[idx][h], l[idx][it]);
    }
    l[idx][h] = max(l[idx][h], m1 + m2);
    return m1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int s1, s2, idx, res = 0x7fffffff;
    maxi = -1; dfs1(1, -1, 0, -1); s1 = t;
    maxi = -1; dfs1(s1, -1, 0, -1); s2 = t;
    dfs2(s2, -1, 0);
    dfs2(s1, -1, 1);
    maxi = -1; dfs1(s1, -1, 0, s2);
    for (int i = 1, tl; i <= maxi; i++) {
        tl = max({ (l[0][vis[i - 1]] + 1) / 2 + (l[1][vis[i]] + 1) / 2 + 1,
            l[0][vis[i - 1]],l[1][vis[i]] });
        if (res > tl) res = tl, idx = i;
    }
    s1 = vis[idx - 1]; s2 = vis[idx];
    int h1, h2, r1, r2;
    ck[s2] = 1;
    maxi = -1; dfs1(s1, -1, 0, -1); h1 = t;
    maxi = -1; dfs1(h1, -1, 0, -1); h2 = t;
    maxi = -1; vck = 0; dfs1(h1, -1, 0, h2); r1 = vis[maxi / 2];
    ck[s2] = 0; ck[s1] = 1;
    maxi = -1; dfs1(s2, -1, 0, -1); h1 = t;
    maxi = -1; dfs1(h1, -1, 0, -1); h2 = t;
    maxi = -1; vck = 0; dfs1(h1, -1, 0, h2); r2 = vis[maxi / 2];
    printf("%d\n%d %d\n%d %d", res, s1, s2, r1, r2);
    return 0;
}