Tree Queries solution codeforces

Tree Queries solution codeforces

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

You have to process qq queries. In each query, you are given a vertex of the tree vv and an integer kk.

To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex vv. 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)mkc(v)−m⋅k (where c(v)c(v) is the resulting number of children of the vertex vv, and mm 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

Tree Queries solution codeforces

The first line contains one integer nn (1n21051≤n≤2⋅105) — the number of vertices in the tree.

Then n1n−1 lines follow, the ii-th of them contains two integers xixi and yiyi (1xi,yin1≤xi,yi≤nxiyixi≠yi) — the endpoints of the ii-th edge. These edges form a tree.

The next line contains one integer qq (1q21051≤q≤2⋅105) — the number of queries.

Then qq lines follow, the jj-th of them contains two integers vjvj and kjkj (1vjn1≤vj≤n0kj21050≤kj≤2⋅105) — the parameters of the jj-th query.

Output

Tree Queries solution codeforces

For each query, print one integer — the maximum value of c(v)mkc(v)−m⋅k you can achieve.

Example
input

Copy
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
output

Tree Queries solution codeforces

Copy
5
2
1
4
0
4
Note

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

Answers to the queries are obtained as follows:

Tree Queries solution codeforces

  1. v=1,k=0v=1,k=0: you can delete vertices 77 and 33, so the vertex 11 has 55 children (vertices 22445566, and 88), and the score is 520=55−2⋅0=5;
  2. v=1,k=2v=1,k=2: you can delete the vertex 77, so the vertex 11 has 44 children (vertices 334455, and 66), and the score is 412=24−1⋅2=2.
  3. v=1,k=3v=1,k=3: you shouldn’t delete any vertices, so the vertex 11 has only one child (vertex 77), and the score is 103=11−0⋅3=1;
  4. v=7,k=1v=7,k=1: you can delete the vertex 33, so the vertex 77 has 55 children (vertices 22445566, and 88), and the score is 511=45−1⋅1=4;
  5. v=5,k=0v=5,k=0: no matter what you do, the vertex 55 will have no children, so the score is 00;
  6. v=7,k=200000v=7,k=200000: you shouldn’t delete any vertices, so the vertex 77 has 44 children (vertices 334455, and 66), and the score is 40200000=44−0⋅200000=4.
  7. For Solution

    Click Here!

Leave a Comment