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
- The depth can be close to the number of nodes.
- Every
vin a query is a label in the tree. - 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