Strawberry Harvest on a Tree

Given an unweighted tree T with n nodes numbered from 1 to n, and k strawberries placed on k distinct nodes, two players (M and B) start at node 1 at time 0. Starting from time 1, at the beginning of each time step each player may either move to an adjacent node or stay at the current node. At the end of every time step, if either player is at a node containing a strawberry, that strawberry is considered collected.

The goal is to collect all strawberries and have both players return to node 1 by the end of some time T. Compute the minimum possible integer time T so that there exists a strategy for the two players to achieve this.

Note: The players move simultaneously. They are allowed to wait at a node. A strawberry is collected if, at the end of any time step, at least one player is on its node. However, by time T both players must be at node 1.

Hint: One way to think about the problem is to first prune the tree to the minimal subtree that contains node 1 and all strawberry nodes. In a one‐player scenario, the minimum required time would be twice the sum of the edges in this subtree (since the player must go out and come back). With two players working in parallel, the two tours can share the common parts near the root. The problem reduces to partitioning the branches (each branch cost being the round‐trip time from a node to its descendant subtree) between the two players so that the maximum time of the two tours is minimized.

inputFormat

The first line contains two integers n and k (2 ≤ n ≤ 100, 1 ≤ k ≤ n). The next n-1 lines each contain two integers u and v indicating an edge between nodes u and v in the tree. The last line contains k distinct integers, representing the nodes that contain a strawberry.

outputFormat

Output a single integer: the minimum time T by which all strawberries can be collected and both players have returned to node 1.

sample

2 1
1 2
2

2