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 on the path from the root1down tos, counting both ends.
Implement path_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)]
path_queries(4, values, edges, [("sum", 4), ("sum", 2), ("set", 3, 0), ("sum", 4)])
# [17, 6, 15]
Constraints: 1 <= n <= 2 * 10^5, up to 2 * 10^5 queries, values between -10^9 and 10^9.
Walking up from s is O(depth) per query, and pushing each change down through a whole subtree is O(n) per update. Aim for O(log n) per query after O(n) preprocessing. The tree can be a single chain of 2·10^5 nodes, so avoid deep recursion.
Show hint
Turn the question around: which nodes' answers does changing v affect? Exactly those in v's subtree. If you number nodes so that every subtree is a contiguous block, an update becomes "add to a range" and a query becomes "read one position".