Tree Queries

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 Kree$ $”$ 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 $reelist$. 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 $N1$ 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.Author:  vishesh345 
Tags  vishesh345 
Date Added:  6012019 
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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions