FastPrep
Problem · Tree

Save the Universe

Learn this problem
● HardRubrikINTERNOA

Problem statement

The n universes form a tree rooted at universe 1. Universe i has positive evilness e[i]. For every universe after the root, p gives its parent.

Partition all vertices into vertical branches. Each branch is a non-empty downward path: consecutive vertices in the branch must be connected by a parent-child edge. Every vertex belongs to exactly one branch.

Each branch must contain at most m universes and have total evilness at most k.

Sample partition

1. Original tree

Sample universes grouped by tree level
LevelLeft sideRight side
0Universe 1 · evilness 1
1Universe 2 · evilness 100Universe 3 · evilness 1
2Universe 4 · evilness 1, child of 2Universes 5, 6 · evilness 1 each, children of 3

2. Cut three edges

Cut 1–2, 2–4, and 3–5. Keep 1–3 and 3–6, so one downward path remains while the other universes become single-vertex branches.

3. Resulting vertical branches

An optimal partition into four branches
BranchDownward pathSizeEvilness sum
11 → 3 → 633
221100
3411
4511

Every branch has at most m = 3 universes and total evilness at most k = 100, so the minimum answer is 4.

Return the minimum possible number of branches, or -1 if even a single vertex violates the evilness limit.

Function

saveTheUniverse(n: int, m: int, k: long, e: long[], p: int[]) → int

Examples

Example 1

n = 6m = 3k = 100e = [1, 100, 1, 1, 1, 1]p = [1, 1, 2, 3, 3]return = 4

Universe 2 must form a branch by itself because its evilness already equals k. One optimal partition is [1, 3, 6], [2], [4], and [5].

Constraints

  • 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

    • More Rubrik problems

    drafts saved locally
    public int saveTheUniverse(int n, int m, long k, long[] e, int[] p) {
  // write your code here
}
    n6
    m3
    k100
    e[1, 100, 1, 1, 1, 1]
    p[1, 1, 2, 3, 3]
    expected4
    checking account