Caravan Kth Halt Problem

Caravan Kth Halt Problem — ExecCode Hard DSA Practice

Solve the Caravan Kth Halt problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

A caravan walks the unique path from city u toward city v. The 0-th halt is u itself. They want the city after exactly k steps along that path. Binary lifting (or HLD) finds the k-th node in logarithmic time after LCA preprocessing. Each query is [u, v, k]. Return that node, or -1 if the path has fewer than k+1 vertices. You are given: n — cities edges — tree edges queries — list of [u, v, k] Return one node index per query, or -1. k = 0 always returns u when u is reachable from itself, which it is.

Examples

Input {'n': 4, 'edges': [[0, 1], [1, 2], [1, 3]], 'queries': [[2, 3, 0], [2, 3, 1], [2, 3, 2], [2, 3, 3]]}; Output [2, 1, 3, -1]. Input {'n': 2, 'edges': [[0, 1]], 'queries': [[0, 0, 0]]}; Output [0]. Input {'n': 3, 'edges': [[0, 1], [0, 2]], 'queries': [[1, 2, 2]]}; Output [2]

Constraints

k >= 0 Tree is connected

Practice Caravan Kth Halt free on ExecCode. Browse DSA problems, topic map, and placement guides.