Company: uber_6feb
Difficulty: medium
Uber Hierarchical Spatial Indexing Uber partitions the world into hexagonal zones with a Hierarchical Spatial Indexing system. Every zone sits inside a larger zone, so the zones form a rooted tree: the root is the whole world, and each finer hexagon hangs below the coarser one that contains it. There are n zones, numbered 0 to n - 1 . Zone i has parent parents[i] , and the single root zone is marked by parents[i] = -1 . The depth of a zone is its distance from the root, so the root has depth 0 , its children have depth 1 , and so on. An audit asks a series of questions of the form startZone resolutionJump . For one such question, look at every zone in the subtree of startZone — that is startZone itself together with all zones nested inside it, at any level — and add up the IDs of those zones whose depth is a multiple of resolutionJump . Depth is always counted from the global root , not from startZone . Answer every question. Input Format The first line contains an integer t , the numb