Harvest k Tiers Below

A terraced orchard is laid out as a binary tree: every terrace (a node with a distinct integer label, which is also its yield) feeds at most two terraces directly below it.

Each query [v, k] asks for the total yield of the terraces that lie exactly k levels below v inside v's own subtree (that is, descendants of v whose depth is depth(v) + k). k = 0 means v alone. If there are no such terraces the answer is 0.

Return the answers in query order.

Examples

        1
       / \
      2   3
     / \   \
    4   5   6
       / \
      7   8

Input:  root = build_tree([1, 2, 3, 4, 5, None, 6, None, None, 7, 8]),
        queries = [[1, 2], [2, 1], [2, 2], [3, 2], [5, 0]]
Output: [15, 9, 15, 0, 5]
Explanation: two levels below 1 are 4, 5 and 6; two levels below 3 there is nothing.

Constraints

• 1 <= number of nodes <= 10**5; the depth can be close to the number of nodes.
• 0 <= len(queries) <= 10**5; every v is a label in the tree and 0 <= k <= 10**5.
• Labels are distinct integers with |label| <= 10**9.
• Target complexity: O((n + q) log n).

Goals

• Number nodes by an explicit-stack preorder so each subtree is a contiguous range
• Keep, for every depth, the preorder numbers and running sums of that level
• Answer each 'k levels below v' query with two binary searches