Path Kth Persistent Problem

Path Kth Persistent Problem — ExecCode Hard DSA Practice

Solve the Path Kth Persistent 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

Tree nodes hold values. On the path u–v, what is the k-th smallest value (0-based)? Persistent segment trees at each node store the root-to-node multiset; two prefixes plus the LCA recover the path. Heavy-light plus a persistent tree is the same idea on chains. Queries [u, v, k]. Return that order statistic or -1 if k is out of range. You are given: n — nodes edges — tree values — node values queries — [u, v, k] Return one value per query. k = 0 is the minimum on the path.

Examples

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

Constraints

Path includes u and v Duplicates keep their multiplicity

Practice Path Kth Persistent free on ExecCode. Browse DSA problems, topic map, and placement guides.