The Tree of Life and Beyond

All submissions for this problem are available.
Dr Brand, wondering about the possibility of executing Plan A, has mapped the possible planets humans can take over in the future, their distance from earth and the resources they have as has a rooted tree rooted at earth $T$ with $N$ nodes and a maximum height of $60$, and each node has a value $V$. You can select any set of nodes $S$, which are connected (ie $S$ is a subgraph of $T$). Let us define these quantities:  value($S$) = sum value of nodes in the set $S$.  cost($S$) = ceil(diameter($S$)/2).  diameter($S$) = the length of the longest path in $S$.  ceil($n$) = the smallest integer greater than or equal to $n$. Dr Brand wants to generate a set $S$ (as discussed above), such that value($S$)>=$k$ and cost($S$) is the minimum possible, and $k$ is a constant. Since he is on his deathbed, he wants you to calculate the minimum cost of the selected set $S$. Note: Diameter of a tree with one node is considered to be $0$. ###Input format  The first line has two space separated numbers $N$ and $k$.  The second line has N space separated numbers where $i^{th}$ number denotes the value of node $i$. The nodes in the tree are $0$ indexed.  The third line has a single integer, the root of the tree.  The next $N1$ lines have two numbers $x$ and $y$ each, denoting an edge between node $x$ and node $y$. ###Constraints  $1 \leq N \leq 10^5$  $1 \leq k \leq 10^{14}$  $1 \leq V \leq 10^9$ for each node ###Output Format Print one line, containing an integer for the minimum possible cost of the set. If there is no such set, print $1$. ###Sample Input 6 15 4 3 4 5 2 3 0 0 1 0 2 1 3 1 4 2 5 ###Sample Output 2Author:  shriram_c253 
Tags  shriram_c253 
Date Added:  30122019 
Time Limit:  1 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 