PublicTransitHard | Topcoder Archive

Problem Statement

Note that this problem has a time limit of 3 seconds.

The city of Treeonto is a tree of N vertices numbered from 0 to N-1. For each valid i, an edge connects vertex i+1 and vertex edges[i]. Travelling along an edge in the graph takes one minute.

The citizens of Treeonto are upset that it takes too long to get around, so they have decided to build a teleporter. The teleporter will consist of two identical booths, each located in some vertex. If a citizen enters either booth, he or she may choose to teleport to the other booth instantly. It is allowed to build both booths in the same vertex.

We define the distance between two vertices as the smallest number of minutes needed to get from one vertex to the other. Let D be the maximum distance between any two vertices. Return the number of ways to place the teleporter such that D does not exceed X.

Definition

Class:: PublicTransitHard
Method:: countValidTeleporters
Parameters:: int, int[], int
Returns:: int
Method signature:: int countValidTeleporters(int N, int[] edges, int X)
(be sure your method is public)

Constraints

N will be between 1 and 2000, inclusive.
edges will contain N-1 elements.
For each valid i, edges[i] will be between 0 and i, inclusive.
X will be between 0 and N, inclusive.

Examples

```
4
```
```
{0, 1, 2}
```
```
1
```
```
Returns: 1
```
```
3
```
```
{0, 0}
```
```
2
```
```
Returns: 6
```
Any teleporter placement is valid.
```
6
```
```
{0, 0, 0, 1, 1}
```
```
2
```
```
Returns: 1
```
```
7
```
```
{0, 1, 0, 1, 2, 4}
```
```
3
```
```
Returns: 0
```

{0, 1, 0, 2, 0, 0, 4, 5, 8, 9, 10, 11, 8, 4, 6}

Returns: 31

{0, 1, 1, 3, 1, 5, 1, 0, 8, 8, 10, 10, 12, 10, 10, 8, 16, 16, 18, 19, 19, 21, 19, 19, 24, 25, 25, 27, 18, 0, 30, 30, 30, 33, 34, 34, 34, 30, 38, 39, 39, 38, 42, 43, 0, 45, 45, 45, 48, 45, 45, 51, 45, 53, 54}

Returns: 610

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.