Gusagwa City

Time limit3sMemory limit512 MB

Summary

Given a tree of N vertices, count the ways to place two teleport booths (possibly on the same vertex) so that the maximum pairwise travel distance is at most X.

Level: Medium7 of 10
Topics: Tree, Shortest path, Brute force
Solved: No attempts yet

문제

Gusagwa City can be represented as a tree with $N$ vertices. The vertices are numbered from 0 to $N-1$ , and for every $0 \le i < N-1$ , vertex $i+1$ is connected to vertex $A_i$ by an edge. Moving along an edge from one vertex to another takes 1 minute.

The citizens of Gusagwa City decided to install teleport devices to reduce travel time. A teleport device has two identical booths, and each booth must be placed on a vertex. When you enter one booth, you immediately come out of the other booth. Both booths may be placed on the same vertex.

The distance between two vertices is the minimum time needed to travel from one to the other. Given $N$ , the edges, and an integer $X$ , let $D$ be the maximum distance over all pairs of vertices. Count the number of ways to install the teleport device so that $D$ does not exceed $X$ .

입력

The first line contains two integers $N$ and $X$ . The second line contains $N-1$ integers $A_i$ .

출력

Print the number of ways to install the teleport device so that $D$ does not exceed $X$ .

제한

$2 \le N \le 2,000$
$0 \le X \le N$
$0 \le A_i \le i$ ( $0 \le i < N-1$ )

Examples5

Example 1
Input
```
4 1
0 1 2
```
Expected output
```
1
```
Example 2
Input
```
3 2
0 0
```
Expected output
```
6
```
Example 3
Input
```
6 2
0 0 0 1 1
```
Expected output
```
1
```
Example 4
Input
```
7 3
0 1 0 1 2 4
```
Expected output
```
0
```

Example 5

Input

16 7
0 1 0 2 0 0 4 5 8 9 10 11 8 4 6

Expected output