Potion Collection on a Tree Map

You are playing your favorite mobile game. In order to have a chance at defeating the legendary Cow Boss, you are trying to farm potions. The game map consists of \(N\) (\(2 \le N \le 10^5\)) rooms numbered from \(1\) to \(N\). The rooms are connected by \(N-1\) edges forming a tree structure.

You explore the map by performing a series of traversals. A traversal is defined as a simple path from room \(1\) to any other room in the tree. After finishing a traversal, you restart from room \(1\) for the next one. Once every room of the tree has been visited in at least one traversal, the map is considered cleared. Your primary goal is to clear the map using the minimum number of traversals.

Your secondary goal is to collect as many potions as possible. Before each traversal begins, a potion appears in one of the rooms. You know in advance the potion location for the next \(N\) traversals. In a given traversal, if you visit the room where the potion appears, you can pick it up. However, if you do not pick it up during that traversal, the potion disappears and cannot be collected later.

If you must clear the map using the minimum number of traversals, what is the maximum number of potions you can collect?

Problem Analysis

Since the map is a tree rooted at room \(1\), note that the unique simple path from \(1\) to any leaf is predetermined. In order to cover every room, every leaf (except room \(1\) if it is a leaf) must be visited in some traversal. Therefore, the minimum number of traversals equals the number of leaves (with the exception that if room \(1\) is a leaf then the minimum number is the total number of leaves minus one).

For each leaf \(L\), the traversal is exactly the unique path from \(1\) to \(L\). A potion that appears in a room \(x\) can be collected in the traversal corresponding to leaf \(L\) if and only if \(x\) lies on the path from \(1\) to \(L\) (i.e. \(x\) is an ancestor of \(L\) when the tree is rooted at \(1\)).

You are given the potion appearance locations for \(N\) rounds. However, you will only perform as many traversals as necessary (i.e. one for each leaf as discussed). You can choose which rounds to associate with which traversal. Each round provides one available potion – and a potion can only be used for one traversal. Thus, the problem reduces to a maximum matching between the set of traversals (leaves) and the rounds (potions), where a leaf \(L\) can be matched with a round in which the potion appears in a room that is on the unique path from \(1\) to \(L\).

This problem can be solved using a greedy DFS strategy on the tree. First, count the number of potions appearing at each room. Then, perform a DFS starting from room \(1\) while maintaining the available potion counts on the current root-to-node path. When a leaf is reached, if there is any available potion along its path (choosing the one deepest in the path, since those are less flexible), assign that potion to cover the leaf and decrement its count. The sum over all leaves gives the maximum number of potions collected.

inputFormat

The first line contains an integer \(N\) representing the number of rooms and the number of rounds. \(N\) is followed by \(N-1\) lines, each containing two integers \(u\) and \(v\) describing an edge connecting rooms \(u\) and \(v\). The last line contains \(N\) integers where the \(i\)th integer indicates the room in which the potion appears in the \(i\)th round.

Note: The tree is guaranteed to be connected and acyclic.

outputFormat

Output a single integer, the maximum number of potions you can collect while clearing the map in the minimum number of traversals.

sample

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

3