Optimum Selection

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 .
Example :
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.
Input
 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 n1 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
Output
 For each test case, output a single line containing the maximum possible sum of values of the selected items
Constraints
 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
Example
Input: 1 3 1 1 2 1 3 6 1 5 1 4 1 Output: 6
Explanation
Example case 1: We can select only 1 item. So, we select it from node 1 as it has maximum value
Author:  kshitijbathla 
Tags  kshitijbathla 
Date Added:  8032016 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions