TreeCutting | Topcoder Archive

Problem Statement

Wolf Sothe has an undirected tree with N vertices, numbered 0 through N-1. You are given the description of the tree as a int[] par with N-1 elements. For each valid i, the tree contains the edge between vertices (i+1) and par[i]. (Note that for your convenience par[i] is always smaller than i+1.)

Some of the vertices contain a positive integer, others are empty. You are given a int[] num with N elements. For each valid i, num[i] is either the number written in vertex i, or -1 if vertex i is empty.

Sothe can modify the tree by cutting some of its edges. Sothe's goal is to reach a configuration with the following properties:

Each connected component contains exactly one vertex with an integer.
The number of vertices in each component is equal to the only integer in that component.

Return "POSSIBLE" (quotes for clarity) if Sothe can reach some configuration with the desired properties by cutting zero or more edges. Otherwise, return "IMPOSSIBLE". Note that the return value is case-sensitive.

Definition

Class:: TreeCutting
Method:: can
Parameters:: int[], int[]
Returns:: String
Method signature:: String can(int[] par, int[] num)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
par will contain exactly N-1 elements.
For each i, the i-th element of par will be between 0 and i, inclusive.
num will contain exactly N elements.
Each element in num will be either -1 or between 1 and N, inclusive.

Examples

```
{0,1,2,2,2}
```
```
{2,-1,-1,4,-1,-1}
```
```
Returns: "POSSIBLE"
```
This is a tree with 6 vertices. The edges are 1-0, 2-1, 3-2, 4-2, and 5-2. Vertex 0 contains the integer 2, vertex 3 contains the integer 4, and all other vertices are empty. Sothe can reach his goal by cutting the edge 1-2. This will produce two components. In one component we have the vertices {0,1}. One of them contains the number 2 (which is also the size of this component) and the other is empty. In the other component we have the vertices {2,3,4,5}. One of them contains the number 4 (which is also the size of this component) and the other three are empty.

{0,1,2,2,2}

{3,-1,-1,3,-1,-1}

Returns: "IMPOSSIBLE"

```
{0,1,2,2,2}
```
```
{2,-1,-1,3,-1,-1}
```
```
Returns: "IMPOSSIBLE"
```
The tree has 6 vertices but in any valid final configuration the components must have 2+3 = 5 vertices, which is impossible.

{0,1,2,2,1,5,2,6,6}

{-1,-1,2,-1,1,3,-1,1,1,2}

Returns: "POSSIBLE"

{0,1,2,2,1,5,2,6,6}

{-1,-1,2,-1,1,-1,3,1,1,2}

Returns: "IMPOSSIBLE"

{0,0,0,0,1,1,2,3,3,3,4,4,4,5,9,9,14,14,14,16,20}

{-1,3,-1,-1,-1,-1,-1,1,1,-1,-1,-1,3,1,-1,1,8,-1,-1,4,-1,-1}

Returns: "POSSIBLE"

{0,0,0,0,1,1,2,3,3,3,4,4,4,5,9,9,14,14,14,16,20}

{-1,2,-1,-1,-1,-1,-1,1,1,-1,-1,-1,3,1,-1,1,9,-1,-1,4,-1,-1}

Returns: "IMPOSSIBLE"

{0,0,1,1}

{-1,-1,5,-1,-1}

Returns: "POSSIBLE"

No cutting necessary.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.