All submissions for this problem are available.
We are given n items with labels from 1 to n . We are also given a special rooted tree with 1 as the root.
At node number i in the special tree , a packet ( Pkt[i] ) having infinite number of items of label i is kept.
A packet ‘Pkt[i]’ of items is defined by 2 parameters : a[i],b[i]
The value of an item in the packet is a[i] . But the value of 'a[i]' keeps on reducing every time we take an item out of it.
Every time an item is taken out from Pckt[i] , 'a[i]' gets reduced by b[i]^2 .
Let A[i] be the original value of a[i]. We take only 1 item , value is a[i] . Now ‘a[i]’ becomes A[i]-b[i]^2 .
If we take another item , value of this will be new ‘a[i]’ ( A[i] - b[i]^2 ) and now a[i] becomes A[i] - 2*(b[i]^2).
So total value of 2 items is = 2*A[i] - b^2 .
We have to select up to k items, so that :
- For 2 selected items having labels ‘i’ and ‘j’, one should not be an ancestor of other in the special tree.
Note that 2 selected items can have the same label( Ancestors of a node x in the tree are all nodes that appear in the path of ‘root’ to ‘x’ excluding ‘x’ ).
- Sum of values of the selected items is maximized.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- First line of every test case contains 2 integers n and k
- Next n-1 lines contains the description of the special tree. Each line contains 2 integers 'u' and 'v'. This means that u and v have an edge between them
- Next n lines contain the values a[i],b[i] for all the packets of items
- For each test case, output a single line containing the maximum possible sum of values of the selected items
- 1 ≤ T ≤ 10
- 1 ≤ n ≤ 10000
- 1 ≤ k ≤ 1000
- 0 ≤ a[i] ≤ 100
- 1 ≤ b[i] ≤ 100
- 1 ≤ u,v ≤ n
- 1 ≤ Sum of n over all test cases ≤ 10000
Input: 1 3 1 1 2 1 3 6 1 5 1 4 1 Output: 6
Example case 1: We can select only 1 item. So, we select it from node 1 as it has maximum value
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions