Backpack on Tree

There is a rooted tree with n nodes. For each node i, there is an item whose volume is $c_i$ and value is $v_i$ and if node i is not the root, it is guaranteed that $|subtreei| \leq \frac{2}{3}|subtree_{father_i} |$.Bacon wants to pick items in $subtree_s$ so that their total volume is exactly t. Help Bacon determine the maximal total value of items he can pick.

The first line contains one integer T($1 \leq T \leq 40$) and there are exactly T test cases below.

For each test case, the first line contains one integer n ($1 \leq n \leq 2 \times 10^4$).

The following n - 1 lines describe edges in the tree. Each line contains two integers  $a_i$ and $b_i (1 \leq a_i,b_i \leq n,a_i \neq b_i)$ describing an edge of the tree.

For the following n lines, the i-th line contains two integers $c_i$ and $v_i (1 \leq c_i \leq 5,1 \leq v_i \leq 10^9)$.

Next line contains one integer the number of queries Q and each of the following Q lines contains two integers $s_i$ and $t_i (1 \leq s_i \leq n, 1 \leq t_i \leq 10^5)$ as a query.

Note that node 1 is the root of the tree.

There is no more than 4 test cases that n is greater than $10^4$, and no more than 10  test cases that n is greater than $10^3$. sum of all Q are not greater than $2 \times 10^5$.

For each test case, first line contains "Case #x:", where x indicates the number of test cases (starting from 1).

Then print Q lines and the i-th line contains the answer of the i-th query. Print -1 for the query if there is no way to pick items in $subtree_s$ with total volume t.

2	
5	
1 2
1 3
1 4
1 5
1 1
2 2
3 3
4 4
5 5
3	
1 15
2 2
3 3
5	
1 2
1 3
1 4
4 5
5 123
3 4543
4 21
1 1231
2 12
3	
1 5
5 2
4 4

Case #i：
15	
2	
3	
Case #2:
4555	
12	
-1	

The tree in first case looks like the picture above,

For query subtree_s =1,t= 15,we should pick items in subtree 1. only method is to pick all
items in subtree 1 and get value 15.

2016CCPC东北地区大学生程序设计竞赛 - 重现赛