26088번 - 트리 다듬기

$N$개의 정점과 $N-1$개의 간선으로 구성된 트리가 주어진다. 트리의 각 정점에는 $1$부터 $N$까지의 번호가 중복 없이 매겨져 있다. 트리에 속한 모든 간선의 길이는 1이다.

트리를 구성하는 서로 다른 두 정점 간의 거리 중 최댓값을 트리의 지름이라고 한다.

동건이는 트리에 아래와 같은 작업을 할 수 있다. 한 번의 작업은 아래의 세 단계를 순서대로 수행하는 것을 의미한다.

1. 트리에서 이웃한 두 정점 $s$와 $t$를 선택하여 $s$와 $t$를 잇는 간선을 삭제한다. 간선 삭제 후, $s$가 포함된 트리를 $S$, $t$가 포함된 트리를 $T$라 하자.
2. 트리 $S$에서 정점 $p$를 선택한다.
3. $p$와 $t$를 잇는 간선을 추가하여 두 트리를 다시 하나의 트리로 합친다.

동건이가 작업을 최대 $K$번 할 수 있을 때, 동건이가 얻을 수 있는 트리 중에서 지름이 가장 긴 것의 지름을 구해보자.

첫째 줄에 트리의 정점 개수를 나타내는 정수 $N$과 최대 작업 횟수를 나타내는 정수 $K$가 공백으로 구분되어 주어진다. ($2 \le N \le 100\,000$, $0 \le K \le 100\,000$)

둘째 줄부터 $N-1$개의 줄에 걸쳐 트리를 이루는 간선의 정보를 나타내는 두 정수 $u$, $v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점을 잇는 간선이 존재한다는 의미이다. ($1 \le u, v \le N$, $u \ne v$)

트리를 이루는 모든 간선은 정확히 한 번씩 주어진다.

첫째 줄에 동건이가 얻을 수 있는 트리 중 지름이 가장 긴 트리의 지름을 출력한다.

아래와 같은 트리에 작업을 1회 진행해보자.

1. 트리에서 이웃한 두 정점 $2$와 $4$를 선택하여 $2$와 $4$를 잇는 간선을 삭제한다. 간선 삭제 후, $2$가 포함된 트리를 $S$, $4$가 포함된 트리를 $T$라 하자.

2. 트리 $S$에서 정점 $3$을 선택한다.

3. $3$과 $4$를 잇는 간선을 추가하여 두 트리를 다시 하나의 트리로 합친다.