Meeting Point on a Route

Hard

In the mountains there are n huts numbered 0 to n - 1, linked by the trails in trails: an entry [u, v] is a two-way trail between huts u and v. The trails form a tree, so there is exactly one path between any two huts. A request requests[i] = [start, end, hut] means a group walks the path from start to end, and a friend in hut hut wants to join it. Find the hut on the group's path (including start and end) that is the fewest trail hops away from hut. Return an array whose i-th element is that hut for the i-th request.

Example 1

n=6, trails=[[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], requests=[[0, 3, 5], [3, 2, 0], [5, 4, 5]] → [1, 2, 5]

The route is 0 → 1 → 2 → 3, and from hut 5 the nearest point is 1 (two hops via 4). The route 3 → 2: from 0 it is two hops to 2 and three to 3, so the meeting point is 2. In the third request hut 5 lies on the route itself.

Example 2

n=2, trails=[[0, 1]], requests=[[1, 1, 0]] → [1]

The route is just point 1, so that is the answer.

Constraints

1 ≤ n ≤ 1000
len(trails) = n - 1, trails[i] = [u, v], 0 ≤ u, v ≤ n - 1, u ≠ v
The trails form a tree
1 ≤ len(requests) ≤ 1000
requests[i] = [start, end, hut], 0 ≤ start, end, hut ≤ n - 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Array

Similar problems

Tree Height After Cutting a Branch Hard Stop a Process Branch Medium Smallest Shared Territory Medium Prune Zero-Weight Branches Medium Rooms Open from the Hall Medium

Input

n=6, trails=[[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]], requests=[[0, 3, 5], [3, 2, 0], [5, 4, 5]]

Expected

[1, 2, 5]

Run checks the first 3 tests in your browser. Submit checks all 80 tests on the server, hidden ones included.