A tree has n nodes numbered 1..n and is rooted at node 1. Node i holds the value values[i - 1]. edges lists the n - 1 undirected edges (a, b).
Process queries in order. Each one is either:
("set", s, x): change the value of nodestox.("sum", s): report the sum of the values in the subtree ofs(splus all of its descendants).
Implement subtree_queries(n: int, values: list[int], edges: list[tuple[int, int]], queries: list[tuple]) -> list[int], returning the answers to the "sum" queries in order.
# 1
# / \
# 2 3
# |
# 4
values = [5, 1, 2, 10]
edges = [(1, 2), (3, 1), (4, 3)]
subtree_queries(4, values, edges, [("sum", 3), ("sum", 1), ("set", 4, -1), ("sum", 3)])
# [12, 18, 1]
Constraints: 1 <= n <= 2 * 10^5, up to 2 * 10^5 queries, values between -10^9 and 10^9.
Summing a subtree by walking it is O(n) per query; aim for O(log n) per query after O(n) preprocessing. The tree can be a single chain of 2·10^5 nodes, which overflows Python's recursion limit.
Show hint
Number the nodes in the order a depth-first search first visits them. In that numbering, every subtree occupies one contiguous block, so a subtree sum becomes a range sum over an array with point updates.