페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6217
서브태스크

탐험가 정올이 2s 1024MB

문제

정올이는 탐험가가 되어 포션을 모으려 한다. 맵은 N개의 방으로 이루어져 있으며, 1번부터 N번까지 번호가 매겨져 있다. 이 방들은 N-1개의 간선으로 연결되어 있으며, 트리 형태를 이룬다.

정올이는 "탐험"이라는 일련의 행동을 통해 맵을 탐험할 수 있다. 탐험은 트리에서 방 1에서 시작하여 다른 방으로 이동하는 단순 경로이다. 한 번의 탐험을 마치면 다시 방 1에서 새로운 탐험을 시작할 수 있다. 모든 방을 최소한 한 번 방문하여 맵을 완성하는 것이 목표이며, 이때 필요한 탐험의 횟수를 최소화해야 한다.

부차적인 목표는 가능한 한 많은 포션을 모으는 것이다. 매 회차의 탐험에 포션은 맵의 특정 방에 나타나며, 해당 탐험에서 포션이 나타난 방을 방문하면 포션을 획득할 수 있다. 만약 포션을 획득하지 못하면 해당 탐험이 끝날 때 포션이 사라져 이후 탐험에서는 획득할 수 없다.

정올이는 똑똑한 프로그래머로서 게임 파일을 살펴본 결과, 다음 N번의 탐험 전에 포션이 어디에 나타날지 알아낼 수 있었다. 맵을 최소 탐험 횟수로 완성할 때, 맵에서 최대한 모을 수 있는 포션의 개수는 얼마인가?


입력

첫 번째 줄에 맵의 방 개수인 정수 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 줄에는 N개의 정수 p_1, p_2, ..., p_N (1 ≤ p_i ≤ N)이 공백으로 구분되어 주어지며, 여기서 p_i는 i번째 탐험에 포션이 나타나는 방 번호이다.

그다음 N-1개의 줄에는 두 개의 정수 a, b (1 ≤ a, b ≤ N)가 주어지며, 이는 방 a와 b를 연결하는 간선을 나타낸다. 이 간선들은 트리 구조를 이룬다.


출력

맵을 최소한의 탐험 횟수로 완성했을 때, 모을 수 있는 최대 포션 개수를 나타내는 정수를 한 줄에 출력한다.


부분문제

번호 점수 조건
#135점

N \le 1000

#211점

모든 포션은 1번 방에서만 나타난다.

#354점

추가 제약 조건 없음


예제 

5
1 5 4 3 4
1 2
1 3
2 4
1 5
3

이 경우 맵을 완성하기 위해 필요한 최소 탐험 횟수는 3이다.

포션 세 개를 세 번의 탐험으로 모을 수 있는 최적의 계획은 다음과 같다:

  • 탐험 1: 1 → 3 (1번 방에서 포션 획득)

  • 탐험 2: 1 → 5 (5번 방에서 포션 획득)

  • 탐험 3: 1 → 2 → 4 (4번 방에서 포션 획득)



출처

USACO 2024 January Silver

로그인해야 코드를 작성할 수 있어요.