{"raw_statement":[{"iden":"statement","content":"Bob's new favourite toy is a rooted tree that consists of n vertices numbered from 1 to n. The number of the root vertex is 1. The tree has l leafs (the root is not considered to be a leaf). Each leaf of the tree has an integer written in it.\n\nThis birthday Bob received n - l stickers as a gift: k of them are labelled \"min\", and the other n - l - k are labelled \"max\". Bob has decided to place the stickers on the internal vertices of the tree, a single sticker on each internal vertex.\n\nOnce he has placed all the stickers on the tree, Bob would like to calculate a function f for each vertex v of the tree in the following fashion: \n\nBob isn't yet sure how to place his stickers on the tree, but he is interested in the value of f in the root vertex. Given the tree and the stickers, help Bob calculate the minimum and the maximum possible value of f(1)!\n\nThe first line contains two space-separated integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ n). The second line contains n - 1 space-separated integer numbers p2, p3, ..., pn (1 ≤ pi ≤ n). The number pi denotes the parent of the vertex numbered i. The third line contains n space-separated integer numbers a1, a2, ..., an (0 ≤ ai ≤ 109). If the vertex i is a leaf, then ai is the number written in that vertex. Otherwise ai will be equal to 0.\n\nIt is guaranteed that the given graph will be a tree. It is guaranteed that k + l ≤ n.\n\nIn a single line output two integers separated by a space — the minimum and the maximum possible value of f(1).\n\nA #cf_span(class=[tex-font-style-underline], body=[tree]) is a connected graph that has no cycles. A rooted tree is a tree with one vertex being the #cf_span(class=[tex-font-style-underline], body=[root vertex]). In a rooted tree, a vertex u is a #cf_span(class=[tex-font-style-underline], body=[child]) of v if and only if there is an edge between v and u, and u does not belong to the path that connects the root vertex with v. The vertex v then is called the #cf_span(class=[tex-font-style-underline], body=[parent]) of u. A vertex of a rooted tree is called a #cf_span(class=[tex-font-style-underline], body=[leaf]) if and only if it has no children. Otherwise the vertex is called an #cf_span(class=[tex-font-style-underline], body=[internal vertex]).\n\n"},{"iden":"input","content":"The first line contains two space-separated integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ n). The second line contains n - 1 space-separated integer numbers p2, p3, ..., pn (1 ≤ pi ≤ n). The number pi denotes the parent of the vertex numbered i. The third line contains n space-separated integer numbers a1, a2, ..., an (0 ≤ ai ≤ 109). If the vertex i is a leaf, then ai is the number written in that vertex. Otherwise ai will be equal to 0.It is guaranteed that the given graph will be a tree. It is guaranteed that k + l ≤ n."},{"iden":"output","content":"In a single line output two integers separated by a space — the minimum and the maximum possible value of f(1)."},{"iden":"examples","content":"Input6 11 1 2 2 30 0 0 1 3 2Output2 3"},{"iden":"note","content":"A #cf_span(class=[tex-font-style-underline], body=[tree]) is a connected graph that has no cycles. A rooted tree is a tree with one vertex being the #cf_span(class=[tex-font-style-underline], body=[root vertex]). In a rooted tree, a vertex u is a #cf_span(class=[tex-font-style-underline], body=[child]) of v if and only if there is an edge between v and u, and u does not belong to the path that connects the root vertex with v. The vertex v then is called the #cf_span(class=[tex-font-style-underline], body=[parent]) of u. A vertex of a rooted tree is called a #cf_span(class=[tex-font-style-underline], body=[leaf]) if and only if it has no children. Otherwise the vertex is called an #cf_span(class=[tex-font-style-underline], body=[internal vertex])."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of vertices in a rooted tree with root at vertex 1.  \nLet $ l = |\\{ i \\in \\{1, \\dots, n\\} \\mid \\text{vertex } i \\text{ is a leaf} \\}| $ be the number of leaves.  \nLet $ k \\in \\mathbb{Z} $, $ 0 \\leq k \\leq n $, be the number of \"min\" stickers; the remaining $ n - l - k $ stickers are \"max\".  \nLet $ P = (p_2, p_3, \\dots, p_n) $, where $ p_i $ is the parent of vertex $ i $, defining the tree structure.  \nLet $ A = (a_1, \\dots, a_n) $, where $ a_i \\in \\mathbb{Z}_{\\geq 0} $: if vertex $ i $ is a leaf, $ a_i $ is its value; otherwise $ a_i = 0 $.  \n\nLet $ I = \\{ i \\in \\{1, \\dots, n\\} \\mid \\text{vertex } i \\text{ is internal} \\} $, so $ |I| = n - l $.  \nLet $ S_{\\text{min}} \\subseteq I $, $ |S_{\\text{min}}| = k $, be the set of internal vertices assigned \"min\" stickers.  \nLet $ S_{\\text{max}} = I \\setminus S_{\\text{min}} $, $ |S_{\\text{max}}| = n - l - k $, be the set assigned \"max\" stickers.  \n\nDefine function $ f(v) $ recursively:  \n- If $ v $ is a leaf, $ f(v) = a_v $.  \n- If $ v $ is internal:  \n  - If $ v \\in S_{\\text{min}} $, then $ f(v) = \\min_{u \\in \\text{children}(v)} f(u) $.  \n  - If $ v \\in S_{\\text{max}} $, then $ f(v) = \\max_{u \\in \\text{children}(v)} f(u) $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq k \\leq n $  \n3. $ k + l \\leq n $  \n4. Tree is valid: parent array defines a rooted tree with root 1.  \n5. Leaf values: $ 0 \\leq a_i \\leq 10^9 $ for leaf $ i $; $ a_i = 0 $ for internal $ i $.  \n\n**Objective**  \nCompute:  \n$$\n\\min_{S_{\\text{min}} \\subseteq I,\\, |S_{\\text{min}}| = k} f(1) \\quad \\text{and} \\quad \\max_{S_{\\text{min}} \\subseteq I,\\, |S_{\\text{min}}| = k} f(1)\n$$","simple_statement":"You are given a rooted tree with n nodes (root is 1). Some nodes are leaves (with given numbers), others are internal. You have k \"min\" stickers and (n - l - k) \"max\" stickers to place on internal nodes (one per node).  \n\nFor each node, define f(v):  \n- If v is a leaf, f(v) = its given number.  \n- If v is internal, f(v) = min of f(children) if it has a \"min\" sticker, or max of f(children) if it has a \"max\" sticker.  \n\nFind the minimum and maximum possible value of f(1) (root) after optimally placing all stickers.","has_page_source":false}