General considerations

• Because of the queries of type "insert ~k~ balls", you might think that you have to insert multiple balls at once to be quick enough. But as there can never be more than ~N~ balls in the machine, and they are only removed one by one, only ~\mathcal O(Q)~ balls are ever added, so it is fine to insert them one by one.
• You can pre-compute for each node the smallest number inside of its subtree. This takes ~\mathcal O(N)~ with one DFS.
• Now you can easily simulate the whole process always taking one step at a time. This approach takes ~\mathcal O(QDR)~ time, where ~D~ is the depth of the tree, and ~R~ the maximum degree of any node. On the balanced-tree lower limit, it is ~D = \mathcal O(\log N)~ and ~R = 2~, so the total time is ~\mathcal O(N \log N)~ which is fine. But on a degenerate tree (i.e. a line), it becomes ~\mathcal O(N^2)~ which is too slow.

Fast Insertion

• After sorting the (direct) children of each node by lowest number in their respective subtree, do another DFS to compute the post-order index of each node.
• These post-order indices are the priorities, by which nodes are getting filled by the add-queries. Therefore you can keep all empty nodes in an appropriate data structure that allows you to find the node to be filled in ~\mathcal O(\log N)~ time. A set or priority queue will both work here.

Fast Deletion

• Let ~p(x)~ denote the parent of node ~x~. You can precompute ~p^{(2^k)}(x)~ for all ~x~ and all appropriate ~k~. This will take ~\mathcal O(N \log N)~ space, and with a little DP ~\mathcal O(N \log N)~ time.
• Now you can speed up the roll-down part of a removal query to only take ~\mathcal O(\log D)~ time.