silver_Potion_Farming — USACO January_Contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 16
Algorithms: greedy, graph theory, tree, dfs, graph traversal

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?
INPUT FORMAT (input arrives from the terminal / stdin):
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 FORMAT (print output to the terminal / stdout):
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.
SAMPLE INPUT:
5
5 4 3 2 1
1 2
1 3
3 4
3 5
SAMPLE OUTPUT:
2
In 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)
SCORING:
Inputs 2-7: $N\le 1000$
Inputs 8-15: No additional constraints.
Problem credits: Suhas Nagar

Starter code: