I recently found this question -
You have a tree of N nodes, and you can do M queries on the tree. The queries are of two types-
1 a x — add a to node x and all its descendents
2 x — find the sum of values of all nodes in the path b/w the root node and the node x (both root and x inclusive).
My brute-force approach — O(N*M)
Made a parent array for parent of each node, and a child vector of sets for children of each node. Also take an upd[n] and val[n] array to keep current pending update and value for each node.
For query 1 (update), just do upd[x] := upd[x] + a
For query 2 (sum from x to root), go backwards from x to root (using parent array), sum all the values along the way, apply val[i] := val[i]+upd[i] (i is b/w root and x) and update upd[y], where y is child of i.
And as expected, it gives TLE for some test cases.
What is a faster approach for this? I am unable to come up with anything that updates and queries in less time.