Dynasty Tree Oracle Problem

Dynasty Tree Oracle Problem — ExecCode Hard DSA Practice

Solve the Dynasty Tree Oracle problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You are given a tree on n nodes, numbered 0 to n-1, rooted at 0. Each node stores an integer. You must answer a mixed stream of path sums, point assignments, and subtree sums. Contest solutions sit in the same family: centroid decomposition for distance aggregates, heavy-light plus a segment tree for path ranges, DSU on tree for subtree multisets, a virtual tree for a sparse set of keys, or a link-cut tree if the forest were dynamic. Process queries in order. Type 0 u v appends the sum of node values on the unique path between u and v. Type 1 u x sets the value of node u to x (it does not append an answer). Type 2 u appends the sum of values in the subtree of u, including u. Return the list of appended answers. You are given: n — number of nodes edges — n-1 undirected tree edges [u, v] values — initial value of each node queries — list of [type, ...] operations Return the sequence of answers from type 0 and type 2 queries. Root is always 0. Path endpoints may be equal. After an update, later queries see the new value.

Examples

Input {'n': 4, 'edges': [[0, 1], [0, 2], [2, 3]], 'values': [1, 2, 3, 4], 'queries': [[0, 1, 3], [2, 2], [1, 2, 10], [0, 1, 3], [2, 0]]}; Output [10, 7, 17, 17]. Input {'n': 1, 'edges': [], 'values': [5], 'queries': [[0, 0, 0], [2, 0]]}; Output [5, 5]. Input {'n': 3, 'edges': [[0, 1], [1, 2]], 'values': [4, 0, -1], 'queries': [[2, 1], [0, 0, 2]]}; Output [-1, 3]

Constraints

1 <= n <= 10^5 in the intended contest bound; path and subtree sums must be logarithmic Queries may mix updates and reads The graph is a tree

Practice Dynasty Tree Oracle free on ExecCode. Browse DSA problems, topic map, and placement guides.