Tree Queries
Contest: Educational Codeforces Round 116 (Rated for Div. 2)
Difficulty rating: 2800
Tags: brute force, dp, trees

You are given a tree consisting of $$$n$$$ vertices. Recall that a tree is an undirected connected acyclic graph. The given tree is rooted at the vertex $$$1$$$.

You have to process $$$q$$$ queries. In each query, you are given a vertex of the tree $$$v$$$ and an integer $$$k$$$.

To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex $$$v$$$. When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of $$$c(v) - m \cdot k$$$ (where $$$c(v)$$$ is the resulting number of children of the vertex $$$v$$$, and $$$m$$$ is the number of vertices you have deleted). Print the maximum possible value you can obtain.

The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

Then $$$n-1$$$ lines follow, the $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — the endpoints of the $$$i$$$-th edge. These edges form a tree.

The next line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow, the $$$j$$$-th of them contains two integers $$$v_j$$$ and $$$k_j$$$ ($$$1 \le v_j \le n$$$; $$$0 \le k_j \le 2 \cdot 10^5$$$) — the parameters of the $$$j$$$-th query.

Output format:
For each query, print one integer — the maximum value of $$$c(v) - m \cdot k$$$ you can achieve.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Note:
The tree in the first example is shown in the following picture:

Answers to the queries are obtained as follows:

1. $$$v=1,k=0$$$: you can delete vertices $$$7$$$ and $$$3$$$, so the vertex $$$1$$$ has $$$5$$$ children (vertices $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$, and $$$8$$$), and the score is $$$5 - 2 \cdot 0 = 5$$$;
2. $$$v=1,k=2$$$: you can delete the vertex $$$7$$$, so the vertex $$$1$$$ has $$$4$$$ children (vertices $$$3$$$, $$$4$$$, $$$5$$$, and $$$6$$$), and the score is $$$4 - 1 \cdot 2 = 2$$$.
3. $$$v=1,k=3$$$: you shouldn't delete any vertices, so the vertex $$$1$$$ has only one child (vertex $$$7$$$), and the score is $$$1 - 0 \cdot 3 = 1$$$;
4. $$$v=7,k=1$$$: you can delete the vertex $$$3$$$, so the vertex $$$7$$$ has $$$5$$$ children (vertices $$$2$$$, $$$4$$$, $$$5$$$, $$$6$$$, and $$$8$$$), and the score is $$$5 - 1 \cdot 1 = 4$$$;
5. $$$v=5,k=0$$$: no matter what you do, the vertex $$$5$$$ will have no children, so the score is $$$0$$$;
6. $$$v=7,k=200000$$$: you shouldn't delete any vertices, so the vertex $$$7$$$ has $$$4$$$ children (vertices $$$3$$$, $$$4$$$, $$$5$$$, and $$$6$$$), and the score is $$$4 - 0 \cdot 200000 = 4$$$.

Example input:
8
6 7
3 2
8 3
5 7
7 4
7 1
7 3
6
1 0
1 2
1 3
7 1
5 0
7 200000

Example output:
5
2
1
4
0
4

Editorial:
A naive solution to this problem would be to implement a recursive function which answers each query: let $$$f(v, k)$$$ be the answer to the query "$$$v$$$ $$$k$$$", we can calculate it as $$$\sum\limits_{u \in children(v)} \max(1, f(u, k) - k)$$$, since for each child $$$u$$$ of vertex $$$v$$$, we either delete it and change the score by $$$f(u, k) - k$$$, or choose to let it remain, and this increases the score by $$$1$$$. Unfortunately, it is too slow.
Let's try to optimize it. First of all, $$$f(v, k-1) \ge f(v, k)$$$ since if we choose the exact same subset of vertices to delete for the query "$$$v$$$ $$$k-1$$$" as we've chosen for the query "$$$v$$$ $$$k$$$", our score won't decrease. Using this fact, we can show that if it's optimal to remove some vertex in the query "$$$v$$$ $$$k$$$", it's also optimal to remove a vertex in the query "$$$v$$$ $$$k-1$$$" because it's optimal to remove vertex $$$u$$$ if $$$f(u, k) - k > 1$$$, and if this condition holds for some value of $$$k$$$, then it holds for each smaller value of $$$k$$$.
Let $$$opt(u)$$$ be the maximum value of $$$k$$$ when it's optimal to remove the vertex $$$u$$$. We will calculate these values for all vertices of the tree using an event processing method: we'll process the values of $$$k$$$ from $$$200000$$$ to $$$0$$$ and use a set or a priority queue to store events of the form "at the value $$$i$$$, vertex $$$u$$$ becomes optimal to delete". This set/priority queue should sort the events in descending order of the value of $$$k$$$, and in case of ties, in descending order of depths of the vertices (to make sure that vertices with the same value of $$$opt(u)$$$ are processed from bottom to up).
Let's analyze the implementation of this process more in detail. For each vertex, we will store two values — the number of vertices we should remove from its subtree, and the number of children this vertex will optimally have. Using these two values, we can easily calculate the value of $$$opt$$$ for a vertex. When a vertex is "removed" (that is, the event corresponding to this vertex is processed), these values for this vertex should be added to its current parent (we can use DSU to find the current parent easily, for example; and don't forget that the number of vertices we have to remove for this new parent also increases by $$$1$$$); then we recalculate the value of $$$opt$$$ for the current parent and change the event corresponding to this current parent (note that the value of $$$opt$$$ for the current parent shouldn't be greater than the value of $$$opt$$$ for the vertex we've deleted).
Okay, this allows us to calculate when it's optimal to delete each vertex. But how do we answer queries? One of the ways to do this is to process queries in the same event processing algorithm (and for every value of $$$k$$$, we first "remove" the vertices $$$u$$$ with $$$opt(u) = k$$$, then process the queries). There is an issue that when we remove a vertex, it can affect the answer not only for its current parent, but also for the vertices that could be its parents, but are already deleted; to handle this, instead of adding the values of the deleted vertex only to the values of its current parent, we perform an addition on the whole path from the vertex to the current parent (excluding the vertex itself). This path addition can be performed with a Fenwick or Segment tree over the Eulerian tour of the tree, and this yields a compexity of $$$O(n \log n)$$$, though with a high constant factor.