- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: February, 2018 -
**Competitors who opened the problem**: 217 -
**Competitors who submitted a solution**: 182 -
**Number of correct solutions**: 110 -
**Accuracy (percentage correct vs those who opened)**: 50.7% -
**Average Correct Time**: 28 minutes, 12 seconds.

- You are given the definition of a tree with weighted nodes in the vectors
**p**and**w**. - Each node may have a maximum of two children.
- The nodes are numbered from 0 to
**w.size()-1**. Node*i's*weight is**w[i]**. - The vector
**p**is a vector of parent id's. Node 0 has no parent. Otherwise, node*i's*parent has an id that is less then*i*. It is specified in**p[i-1]**. - You are playing a solitare game which has the following rules.
- At each step, you may remove a stone from the tree, or add a stone to the tree.
- You may only add a stone to a node if there is a stone on each of its children (or if it's a leaf node).
- The game is over when you add a stone to the root.
- The value of a state of the game is the sum of the weights of all nodes with stones on them.
- The score of a game is the maximum value of any state of the game.
- Return the minimum possible score.
- The maximum size of the tree is 1,000 nodes in Topcoder. I have made that 100,000 in my tests.
- Weights are between 1 and 100,000.
- The class name is
**StonesOnATree**, and the method is:int StonesOnATree::minStones(vector <int> p, vector <int> w);

- Example 0:
p = { 0, 1, 2, 3 } w = { 1, 2, 2, 4, 4 }

The tree is a line 0 - 1 - 2 - 3 - 4. You play the game optimally as follows:- Place the only legal stone you can, onto node
*4*. Let's call that node*i*. - Repeat the following until you have placed a stone onto node 0:
- Place a stone on
*i's*parent. - Remove the stone from
*i*. - Set
*i*to be*i's*parent.

If you play the game in this manner, your optimal score will be 8.

- Place the only legal stone you can, onto node
- Example 1:
p = { 0, 0 } w = { 1, 2, 3 } Answer: 6

- Example 2:
p = { 0 } w = { 100000, 100000 } Answer: 200000

- Example 3:
p = {0, 0, 1, 1, 2, 2} w = {1, 1, 1, 1, 1, 1, 1} Answer: 4

- Example 4:
p = {0, 0, 1, 2, 3, 4, 4, 2, 1, 3, 6, 7} w = {1, 2, 3, 4, 5, 6, 6, 7, 8, 8, 8, 9, 10} Answer: 22

What I did was convert **p** to an *adjacency list* representation. I have
a vector of vectors of integers called **Adj**, where
**Adj[i]** is a vector of the id's of the children of node *i*.
And I stored **w**
in the class in a vector named **W**.

You should stop here and add **Adj** and **W** to the **StonesOnATree** class,
and create them from **p** and **w**. Print them out and verify that they are
correct for the examples.

Next, I wrote added a method called **S()** to the class:

int StonesOnATree::S(int n); |

This solves the problem for the subtree rooted at node *n*.
**S(n)** performs a postorder traversal, so when you call it on a node *n*,
you'll do the following:

- If node
*n*is a leaf, put a stone there. You can easily calculate the return value. - If node
*n*is not a leaf, then you need to call**S()**on each of*n*'s children. When this is done, there are stones in your node's children, and nowhere else in the stubtree, and you have stored solutions for your children. You place a stone in*n*, and in doing so, you can calculate the solution for**S(n)**. You remove the stones from*n's*children, and return the solution.

I'm not telling you how to do this calculation -- I want you to use your logic skills to figure it out.

Here is ASCII art for the last example, which should help you a lot!

--------------------- | N: 0 | | W[0]: 1 | | Adj[0] = { 1, 2 } | | S(0) = 22 | --------------------- / \ /-----/ \-----\ / \ --------------------- --------------------- | N: 1 | | N: 2 | | W[1] = 2 | | W[2] = 3 | | Adj[1] = { 3, 9 } | | Adj[2] = { 4, 8 } | | S(1) = 18 | | S(2) = 22 | --------------------- --------------------- / \ / \ --------------------- --------------------- --------------------- --------------------- | N: 3 | | N: 9 | | N: 4 | | N: 8 | | W[3] = 4 | | W[9] = 8 | | W[4] = 5 | | W[8] = 8 | | Adj[3] = { 5, 10 }| | Adj[9] = {} | | Adj[4] = { 6, 7 } | | Adj[8] = {} | | S(3) = 18 | | S(9) = 8 | | S(4) = 22 | | S(8) = 8 | --------------------- --------------------- --------------------- --------------------- / \ / \ --------------------- --------------------- --------------------- --------------------- | N: 5 | | N: 10 | | N: 6 | | N: 7 | | W[5] = 6 | | W[10] = 8 | | W[6] = 6 | | W[7] = 7 | | Adj[5] = {} | | Adj[10] = {} | | Adj[6] = { 11 } | | Adj[7] = { 12 } | | S(5) = 6 | | S(10) = 8 | | S(6) = 15 | | S(7) = 17 | --------------------- --------------------- --------------------- --------------------- | | --------------------- --------------------- | N: 11 | | N: 12 | | W[11] = 9 | | W[12] = 10 | | Adj[11] = {} | | Adj[12] = {} | | S(11) = 9 | | S(12) = 10 | --------------------- ---------------------