Skip to main content

Morgan Stanley

Morgan Stanley OA-6 2022

Problem Description

A company sells products at N outlets, which are connected to each other by a series of roads. There is only one way to travel between any two outlets. Each outlet has a unique ID, and when the inventory of a certain product reaches a minimum level, K outlets request extra inventory.

The company's warehouse sends these requested products to the outlets, and to minimize fuel consumption, the warehouse supervisor directs the driver, Mike, to deliver products along the shortest and most direct paths without traveling any road twice.

Your task is to help Mike deliver the inventory to the maximum number of outlets in a single trip, ensuring he does not traverse any road more than once.

Input Format:

  • The first line of input consists of an integer num representing the total number of outlets of the company, including the warehouse N.
  • The second line consists of koutletsCount, representing the number of outlets that requested extra inventory K.
  • The third line consists of K space-separated integers representing the outlet IDs of the outlets that requested the extra inventory.
  • The fourth line consists of two space-separated integers: numR, the total number of roads between outlets (always numR = N-1 ), and conOutlet, which represents the number of outlets connected by a single road (this value is always 2).
  • The next numR lines consist of two integers A and B, which represent a road connection between outlets A and B.

Output Format:

  • Print an integer representing the maximum number of outlets Mike can cover in a single trip without traveling any road twice.

Constraints:

  • 0 <= koutletsCount <= 10^5
  • 1 <= num <= 10^5
  • 1 <= A, B <= num
  • numR = num - 1

Example:

Input:

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

Output:

2

Explanation:

In this example, there are four outlets (including the warehouse). Outlets 2, 3, and 4 have requested extra inventory. Mike can only deliver to two outlets in a single trip because delivering to the third outlet would require traveling a road twice, which is not allowed. Thus, Mike can deliver to outlets 2 and 3, or 2 and 4, or 3 and 4, but not all three.

So, the output is 2.