编程介的小学生 2017-06-22 07:40 采纳率: 0.4%
浏览 652
已采纳

Backpack on Tree

Problem Description
There is a rooted tree with n nodes. For each node i, there is an item whose volume is ci and value is vi and if node i is not the root, it is guaranteed that |subtreei|≤23|subtreefatheri|.Bacon wants to pick items in subtrees so that their total volume is exactly t. Help Bacon determine the maximal total value of items he can pick.

Input
The first line contains one integer T(1≤T≤40) and there are exactly T test cases below.

For each test case, the first line contains one integer n (1≤n≤2×104).

The following n - 1 lines describe edges in the tree. Each line contains two integers ai and bi(1≤ai,bi≤n,ai≠bi) describing an edge of the tree.

For the following n lines, the i-th line contains two integers ci and vi(1≤ci≤5,1≤vi≤109).

Next line contains one integer the number of queries Q and each of the following Q lines contains two integers si and ti(1≤si≤n,1≤ti≤105) 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 104, and no more than 10 test cases that n is greater than 103. sum of all Q are not greater than 2×105.

Output
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 subtrees with total volume t.

Sample Input
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

Sample Output
Case #i:
15

2

3

Case #2:
4555

12

-1

展开全部

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-07-21 04:22
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

手机看
程序员都在用的中文IT技术交流社区

程序员都在用的中文IT技术交流社区

专业的中文 IT 技术社区,与千万技术人共成长

专业的中文 IT 技术社区,与千万技术人共成长

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

关注【CSDN】视频号,行业资讯、技术分享精彩不断,直播好礼送不停!

客服 返回
顶部