All submissions for this problem are available.Ross is very fond of Video Games along with Competitive Aptitude. One of his friend suggests him to try a game named $“$ $Tree K-ree$ $”$ which is an application of Tree Data Structure. Everytime a player plays the game, he is provided with a tree on his screen. Let total number of nodes of the tree be $N$ and each node of the tree has some node value. For a particular node $i$ $,$ $“$ $ree - list$ $”$ is a sorted array consisting of node values of all the nodes in the subtree of that particular node $i$ including the node value of the node $i$. Player needs to compute a value called $“$ $ree - value$ $”$ for each node of the tree, which is defined as the $K$$th$ node value in the $ree-list$. If for a given node, $K$ doesn’t exist in its $“$ $ree - list$ $”$, then its $“$ $ree - value$ $”$ will be zero. To win the game, Ross needs to predict sum of $“$ $ree - value$ $”$ of all the nodes of the tree say $S$. Your task is to help Ross in computing this sum $S$. $Note:$Tree is rooted at 1. ###Input: - First line will contain two space separated integers $N$ and $K$. - Next $N-1$ lines contains two space separated integers $X$ and $Y$ denoting an undirected edge between $X$ and $Y$. - Next line contains $N$ space separated integers which denotes the node value. ###Output: Print a single integer denoting sum of all $"$ $ree - value$ $"$ $i.e$ $S$ ###Constraints - $1 \leq N \leq 100000$ - $1 \leq K \leq 100000$ - $0 \leq Node values \leq 100000$ ###Sample Input: 5 2 1 2 1 3 2 4 2 5 3 7 6 2 1 ###Sample Output: 4 ###EXPLANATION: Only node 1 and 2 have greater than equal to $K$ nodes . Answer for 1 is $K=2$$th$ element of array $[$1,2,3,6,7$]$ which is 2 and answer for 2 is 2$nd$ element of array $[$1,2,7$]$ which is 2. Hence answer $=$ 4.
|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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions