레이팅 미적용당신은 좋아하는 모바일 게임을 하며, 전설의 소 보스를 물리칠 기회를 잡기 위해 포션을 파밍하려 한다. 게임 맵은 \(1\dots N\)의 번호가 붙은 \(N\) \((2 \leq N \leq 10^5)\)개의 방이 트리를 이루는 \(N-1\)개의 간선으로 연결된 구조이다.
맵은 여러 번의 "탐색"을 통해 돌아다닐 수 있다. 탐색이란 방 \(1\)에서 트리의 다른 어떤 방까지의 단순 경로이다. 한 탐색을 끝내면 방 \(1\)에서 새로운 탐색을 시작할 수 있다. 모든 방이 적어도 한 번의 탐색으로 방문되면 맵이 완성된다. 주 목표는 최소 횟수의 탐색으로 맵을 완성하는 것이다.
부차적인 목표는 가능한 한 많은 포션을 파밍하는 것이다. 각 탐색이 시작되기 전에 맵의 어떤 방에 포션이 하나 생성된다. 현재 탐색에서 포션이 생성된 방을 방문하면 그 포션을 주울 수 있다. 포션을 줍지 않으면 현재 탐색이 끝날 때 포션이 사라지므로, 이후 탐색에서는 주울 수 없다.
당신은 똑똑한 프로그래머라서 게임 파일을 들여다본 끝에 다음 \(N\)번의 탐색 전에 포션이 어디에 나타날지 알아냈다. 최소 횟수의 탐색으로 맵을 완성한다면, 맵에서 파밍할 수 있는 포션의 최대 개수는 얼마인가?
출제: Suhas Nagar
배점
- 입력 2-7: \(N\le 1000\)
- 입력 8-15: 추가 제약 없음.
출제: Suhas Nagar
입력의 첫째 줄에 맵의 방 개수를 나타내는 정수 \(N\)이 주어진다.
다음 줄에 공백으로 구분된 \(N\)개의 정수 \(p_1 \: p_2 \: \ldots \: p_N\)이 주어진다 (\(1 \leq p_i \leq N\)). \(p_i\)는 \(i\)번째 탐색 전에 포션이 나타날 방이다.
마지막으로 \(N-1\)개의 줄에 방 \(a\)와 \(b\) 사이의 간선을 나타내는, 공백으로 구분된 두 정수 \(a \: b\) \((1 \leq a, b \leq N)\)가 주어진다. 이 간선들이 트리를 이룸이 보장된다.
최소 횟수의 탐색으로 맵을 완성할 때 파밍할 수 있는 포션의 최대 개수를 나타내는 정수 하나를 한 줄에 출력한다.
5
5 4 3 2 1
1 2
1 3
3 4
3 52In this case, the minimum number of traversals required to complete the map is
\(3\).
One optimal plan that picks up two potions in three traversals is as follows:
- Traversal 1: \(1 \rightarrow 3 \rightarrow 5\) (Pick up potion at 5)
- Traversal 2: \(1 \rightarrow 3 \rightarrow 4\) (Pick up potion at 4)
- Traversal 3: \(1 \rightarrow 2\) (Forced to complete the map and ignore potion at 3)
Alternatively, we could have also planned our traversals as follows:
- Traversal 1: \(1 \rightarrow 2\) (no potions)
- Traversal 2: \(1 \rightarrow 3 \rightarrow 4\) (Pick up potion at 4)
- Traversal 3: \(1 \rightarrow 3 \rightarrow 5\) (Pick up potion at 3)
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Silver