402509: GYM100796 C Minimax Tree

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.

This 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.

Once 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:

• If v is a leaf, f(v) is equal to the integer that is written in v.
• If v has a "min" sticker, f(v) is equal to the minimum value of f(u), where u is any child of v.
• If v has a "max" sticker, f(v) is equal to the maximum value of f(u), where u is any child of v.

Bob 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)!

The first line contains two space-separated integers n and k (2 ≤ n ≤ 10⁵, 0 ≤ k ≤ n). The second line contains n - 1 space-separated integer numbers p₂, p₃, ..., p_n (1 ≤ p_i ≤ n). The number p_i denotes the parent of the vertex numbered i. The third line contains n space-separated integer numbers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹). If the vertex i is a leaf, then a_i is the number written in that vertex. Otherwise a_i will be equal to 0.

It is guaranteed that the given graph will be a tree. It is guaranteed that k + l ≤ n.

In a single line output two integers separated by a space — the minimum and the maximum possible value of f(1).

6 1
1 1 2 2 3
0 0 0 1 3 2

2 3

A tree is a connected graph that has no cycles. A rooted tree is a tree with one vertex being the root vertex. In a rooted tree, a vertex u is a 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 parent of u. A vertex of a rooted tree is called a leaf if and only if it has no children. Otherwise the vertex is called an internal vertex.