만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

중첩된 고무줄

시간 제한1초메모리 제한1024 MB

요약
정점 n개로 이루어진 트리가 주어질 때, 서로 인접하지 않은 정점들로 고를 수 있는 가장 큰 집합의 크기를 구합니다.
난이도

보통10점 중 5점

유형
트리, 동적 계획법
정답자
아직 제출이 없습니다

문제

정점이 nn개인 트리가 있다. 이 트리를 무한히 넓은 평면 위의 고무줄 nn개로 바꾸려고 한다. 변환은 다음 규칙을 따른다.

  • 임의의 두 정점 aa와 bb에 대해, 고무줄 aa와 bb는 트리에서 aa와 bb 사이에 간선이 있을 때에만 교차한다.
  • 각 고무줄은 단순 루프 모양이다. 즉, 자기 자신과 교차하지 않는 루프이다.

다음과 같이 정의한다.

  • 고무줄 aa가 고무줄 bb를 포함한다는 것은, 고무줄 bb가 고무줄 aa의 영역 안에 있고 두 고무줄이 서로 교차하지 않는다는 뜻이다.
  • 고무줄의 수열 a1,a2,…,aka_1, a_2, \ldots, a_k (k≥2k \ge 2)이 중첩되어 있다는 것은, 모든 ii (2≤i≤k2 \le i \le k)에 대해 ai−1a_{i-1}이 aia_i를 포함한다는 뜻이다.

위 그림은 변환의 예시이다. 고무줄 55와 66은 중첩되어 있다.

제약 조건을 만족하는 변환과 중첩된 고무줄 수열이 항상 존재함은 증명되어 있다.

주어진 트리에서 얻을 수 있는 중첩된 고무줄 수열의 최대 길이를 구하여 출력하라.

입력

첫 번째 줄에 트리의 정점 수 nn (3≤n≤1053 \le n \le 10^{5})이 주어진다.

이어지는 n−1n-1개의 줄 중 ii번째 줄에는 간선으로 연결된 두 정점 aia_i와 bib_i (1≤ai<bi≤n1 \le a_i \lt b_i \le n)가 주어진다. 주어진 그래프는 nn개의 정점으로 이루어진 트리임이 보장된다.

출력

답을 출력한다.

힌트

첫 번째 입력에서는 아래 변환을 통해 고무줄 11, 22, 55, 66으로 이루어진 길이 44의 중첩 수열을 얻을 수 있다. 길이 44의 중첩 수열을 만드는 다른 변환도 존재한다. 그러나 이 트리로는 길이 55 이상의 중첩 수열을 만들 수 없다.

두 번째 입력에 대한 변환의 한 가지 예는 아래와 같다.

예제2

  1. 예제 1

    입력
    6
    1 3
    2 3
    3 4
    4 5
    4 6
    
    예상 출력
    4
    
  2. 예제 2

    입력
    4
    1 2
    2 3
    3 4
    
    예상 출력
    2