Supply Outposts Minimum Distance
Given a tree of N outposts connected by N-1 bidirectional tunnels, process M queries that either designate an outpost as a Supply Outpost or find the minimum tunnel distance from a given outpost to the nearest Supply Outpost.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late August, 2026
Sara is responsible for managing a network of N outposts connected by N - 1 bidirectional tunnels. Each outpost is identified by a number from 1 to N. Initially, outpost 1 is the only Supply Outpost. A Supply Outpost has an unlimited supply of resources. Sara receives M queries over time. Each query contains two integers: t o where: t = 1: Outpost o becomes a Supply Outpost. t = 2: A command arrives at outpost o. Sara needs to find the minimum distance from outpost o to any Supply Outpost. The distance between two outposts is the minimum number of tunnels that must be traversed to travel from one outpost to the other. Once an outpost becomes a Supply Outpost, it remains a Supply Outpost permanently. Constraints 2 ≤ N ≤ 7 × 10^5 There are exactly N - 1 bidirectional tunnels.
Hello Interview Premium
Your account is free and you can post anonymously if you choose.