Potion Farming
플래티넘 V의견: 0
You are playing your favorite mobile game and you are trying to farm potions so
that you may have a chance at defeating the legendary cow boss. The game map is a
series of \(N\) \((2 \leq N \leq 10^5)\) rooms labeled \(1\dots N\) connected by
\(N-1\) edges that form a tree.
You can explore the map by making a series of "traversals". A traversal is a
simple path from room \(1\) to any other room in the tree. Once you finish one
traversal, you can start another traversal from room \(1\). The map is complete
once every one of its rooms is visited by at least one traversal. Your main goal
is to complete the map in the minimum number of traversals.
Your secondary goal is to farm as many potions as possible. Before a traversal
begins, a potion will spawn at some room in the map. You can pick up the potion
by visiting the room that the potion spawned at in the current traversal. If you
do not pick up the potion, then it will disappear once the current traversal
ends, so you cannot pick it up in future traversals.
As you are a smart programmer, after looking at the game files, you were able to
figure out where the potions will appear before your next \(N\) traversals. If you
complete the map in the minimum number of traversals, what is the maximum amount
of potions that you can farm from the map?
Problem credits: Suhas Nagar
SCORING
- Inputs 2-7: \(N\le 1000\)
- Inputs 8-15: No additional constraints.
Problem credits: Suhas Nagar
The first line of the input contains an integer \(N\), denoting the number of
rooms in the map.
Then follow \(N\) space-separated integers \(p_1 \: p_2 \: \ldots \: p_N\) where
\(1 \leq p_i \leq N\), where \(p_i\) is the room that a potion will appear at before
the \(i\)th traversal.
Finally, \(N-1\) lines follow with two space-separated integers \(a \: b\)
\((1 \leq a, b \leq N)\) representing an edge between rooms \(a\) and \(b\). It is
guaranteed that these edges form a tree.
Output one line containing a single integer, the maximum amount of potions that
you can farm from the map in the minimum number of traversals.
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
평가 및 의견
Potion Farming
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Potion Farming