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;
}
