Least-Privileged Key Unlocking Every Requested Device in a Device Tree

Devices are organized in a tree for access control. Every device except the root has exactly one parent, and the key of a device unlocks that device and all of its descendants: its children, their children, and so on. A key that unlocks more devices carries more privilege, so an access request should be granted the single key with the least privilege that still unlocks every device the request lists. The task was asked in two stages: first for requests of exactly two devices, then for a batch of requests in which each request can list many devices, on a tree of up to 200,000 devices. Write one function that answers a batch of requests of any size; a two-device request is simply a request of length 2. ### Function Signature ```python def least_privileged_keys(parent: list[int], requests: list[list[int]]) -> list[int]: ``` ### Rules - Devices are numbered `0` to `n - 1`, where `n = len(parent)`. `parent[v]` is the parent of device `v`, and `parent[v] == -1` only for the root. The root need not be device `0`. - The key of device `v` unlocks exactly the devices in the subtree rooted at `v`: `v` itself and every device whose chain of parents passes through `v`. - For each request, return the device whose key unlocks every device listed in the request and, among all such keys, unlocks the fewest devices. This device is always unique: it is the deepest device that, for every listed device `d`, is either `d` itself or an ancestor of `d`. - A request can list a single device, whose answer is that device, and can list the same device more than once. - Return one answer per request, in the order of `requests`. ### Constraints - `1 <= n <= 2 * 10^5` - Exactly one `v` has `parent[v] == -1`. Every other `parent[v]` is in `[0, n - 1]`, and following parents from any device reaches the root, so the input is a valid tree with no cycles. - The tree can be arbitrarily deep, up to a single chain of `n` devices. - `1 <= len(requests) <= 2 * 10^5` - Every request lists at least one device, and the total number of device ids across all requests is at most `2 * 10^5`. - Every device id in a request is in `[0, n - 1]`. - All values fit in a 32-bit signed integer. ### Examples **Example 1** (two-device requests) ```text Input: parent = [-1, 0, 0, 1, 1, 2, 4] requests = [[3, 4], [6, 3], [5, 6], [4, 6]] Output: [1, 1, 0, 4] ``` Device `0` is the root, with children `1` and `2`; device `1` has children `3` and `4`; device `2` has child `5`; device `4` has child `6`. Key `1` unlocks `{1, 3, 4, 6}`, which covers both `[3, 4]` and `[6, 3]`, and no key that unlocks fewer devices covers either pair. Devices `5` and `6` sit under different children of the root, so only key `0` covers both. Device `4` is above `6`, so key `4` covers `[4, 6]`. **Example 2** (batched requests with more devices) ```text Input: parent = [3, 3, 0, -1, 1, 1] requests = [[4, 5, 1], [2, 4, 5], [5, 5], [0]] Output: [1, 3, 5, 0] ``` Device `3` is the root, with children `0` and `1`; device `0` has child `2`; device `1` has children `4` and `5`. Key `1` unlocks `{1, 4, 5}`, exactly the first request. The second request mixes device `2`, under `0`, with devices `4` and `5`, under `1`, so only the root's key `3` covers it. The request that lists device `5` twice gets key `5`, and the request `[0]` gets key `0`.