Problem Statement
You are given a rooted tree with n nodes. The nodes are labeled from 0 to n-1. Node 0 is the root.
You are given the description of the tree: the int[]s p and w. The int[] p has n-1 elements. For each valid i, node p[i] is the parent of node (i+1). You may assume that for each i we have p[i] <= i. The int[] w has n elements. For each valid i, w[i] is the weight of node i.
The int[] w has a special property: it is non-decreasing. That is, for each valid i we have w[i-1] ⤠w[i].
All nodes of the tree are currently empty. You are now going to play a game with the tree and an unlimited supply of stones. The game is played in turns. In each turn you can either remove a single stone from anywhere into a tree, or you can place a single stone onto a node of the tree. However, there is a restriction on placing the stones: you may only place a stone onto a node if all of its children currently have stones placed on them. (Note that this means that you can always place a stone onto any leaf of the tree.)
The weight of a given state of the game is equal to the sum of weights of nodes with stones.
You win the game by placing a stone onto the root of the tree. You want to win the game. If there are multiple ways to do so, you prefer a way for which the maximum weight of a state during the game is minimized. Compute and return this weight. In other words, compute and return the smallest W for which there is a way to win the game such that during the game the total weight of nodes with stones never exceeds W.
Definition
- Class:
- StonesOnATreeDiv2
- Method:
- minStones
- Parameters:
- int[], int[]
- Returns:
- int
- Method signature:
- int minStones(int[] p, int[] w)
- (be sure your method is public)
Constraints
- p will have between 1 and 999 elements, inclusive. (Thus, the number of nodes is between 2 and 1,000, inclusive.)
- The i-th element of p[i] will be between 0 and i, inclusive.
- w will have exactly len(p)+1 elements.
- Each element w will be between 1 and 10^5, inclusive.
- Elements of w will be non-decreasing.
Examples
{0,1,2,3}{1,2,2,4,4}Returns: 8
There are five nodes in a line. Here, one optimal solution is as follows: Place stone on node 4 (weight = 4). Place stone on node 3 (weight = 8). Remove stone from node 4 (weight = 4). Place stone on node 2 (weight = 6). Place stone on node 1 (weight = 8). Remove stone from node 2 (weight = 6). Place stone on node 0 (weight = 7). The maximum weight over all states is 8. It can be shown there is no other sequence of moves that has a smaller maximum weight.{0,0,0,0}{1,2,3,4,5}Returns: 15
In order to be able to place a stone onto node 0 we have to place stones onto all four of its children. Thus, at the end of the game each of these five nodes will have a stone.{0}{100000,100000}Returns: 200000
{0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6}{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}Returns: 6
{0,0,1,2,3,4,4,2,1,3,6,7}{1,2,3,4,5,6,6,7,8,8,8,9,10}Returns: 22