A document store describes its folders with three parallel lists:
ids[i]: the (distinct, integer) id of folderi,kids[i]: the ids of the folders directly inside folderids[i](possibly empty),names[i]: the name of folderids[i].
A folder that no other folder lists as a child is a top-level folder, so there may be several independent trees. Every id listed in some kids[i] also appears in ids, each folder has at most one parent, and there are no cycles.
Write folder_path(ids, kids, names, target) -> str that returns the path from the target's top-level folder down to the target, as "/" followed by the folder names joined with "/". If target is not one of the ids, return "".
ids = [7, 3, 12, 5, 9]
kids = [[3, 5], [12], [], [], []]
names = ["home", "docs", "taxes", "music", "tmp"]
folder_path(ids, kids, names, 12) # "/home/docs/taxes"
folder_path(ids, kids, names, 7) # "/home"
folder_path(ids, kids, names, 9) # "/tmp" (another top-level folder)
folder_path(ids, kids, names, 4) # ""
Names need not be unique (two different folders may both be called "notes"), and the lists may be in any order: a child can be listed before its parent.
Up to 10**5 folders, and a hierarchy can be a single chain that deep. Avoid searching the whole list for each step up, and watch out for Python's recursion limit.
Show hint
Build a parent dict (child id -> parent id) and a name dict in one pass. Then walk from the target up through parent until you reach a folder with no parent, collecting names, and reverse them.