FastPrepFastPrep
Problem Brief

Save the Universe

INTERNOA

Rick and Morty, on one of their adventures, entered the 4th Dimension and realized that every universe is connected to another universe to form a tree, with the prime universe at the root of that tree.

Along with this, they also discovered that each universe has an evil number assigned to it.

Now, with their splitting gun, they want to split the tree into vertical branches such that the sum of the evil numbers of all these branches is less than some number k.

However, Rick's gun broke while entering the 4th Dimension and now can break the branch with at most m universes. Your task is to split the tree into the minimum number of branches to save the multiverse.

Input Format

  • The first line contains three integers: n, m, k — the size of the tree, the power of the gun, and the tolerable evilness, respectively.
  • The second line contains n integers e[i], the evil number of each universe, where 1 ≤ e[i] ≤ 10^9.
  • The third line contains n-1 integers p[i], where p[i] is the parent of the (i+1)-th universe.

    • Output Format

    Output one number: the minimum number of branches. If it is impossible to split the tree, output -1.

    1Example 1

    Input
    n = 6, m = 3, k = 100, e = [1, 100, 1, 1, 1, 1], p = [1, 1, 2, 3, 3]
    Output
    4
    Explanation
    Example 1 illustration

    Constraints

    Limits and guarantees your solution can rely on.

  • Number of universes, n ≤ 10^5
  • The power of the gun, m ≤ 10^5
  • The evilness of each universe and total evilness, K ≤ 10^18
    • public int saveTheUniverse(int n, int m, long k, long[] e, int[] p) {
  // write your code here
}
    Input

    n

    6

    m

    3

    k

    100

    e

    [1, 100, 1, 1, 1, 1]

    p

    [1, 1, 2, 3, 3]

    Output

    4

    Sign in to submit your solution.