Given a tree where nodes have positive weights and Q queries:
- X K: Find a node Y such that node X lies in subtree of Y. Assume z=dist(X, Y). Now, sum of all nodes in subtree of Y at a distance of z should be at least K. Your aim is to minimise z.
- X W: Add a new leaf with X as parent and positive weight W.
Explanation: For query, we just need to find an ancestor of X which follows the properties. Now, if the properties are true for certain node p, its also true for parent of p. So, we use binary search.
Level: Medium