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≤N≤105) rooms labeled 1…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 p1p2…pN where 1≤pi≤N, where pi
is the room that a potion will appear at before the ith traversal.
Finally, N−1 lines follow with two space-separated integers ab (1≤a,b≤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→3→5 (Pick up potion at 5)
Traversal 2: 1→3→4 (Pick up potion at 4)
Traversal 3: 1→2 (Forced to complete the map and ignore potion at 3)
Alternatively, we could have also planned our traversals as follows:
Traversal 1: 1→2 (no potions)
Traversal 2: 1→3→4 (Pick up potion at 4)
Traversal 3: 1→3→5 (Pick up potion at 3)
SCORING:
Inputs 2-7: N≤1000
Inputs 8-15: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
