Problem TREEQ

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