시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB927610.345%

문제

You are given a rooted tree consisting of $N$ vertices, along with integers $R$ and $M$. The vertices are numbered from $1$ to $N$, with vertex $1$ as a root. Each of the other vertices has a single parent in the tree.

If a vertex s is chosen, it becomes infected along with all its descendants (i.e. vertices that can be reached by following edges downward from s) at a distance of $R$ or less, where distance is calculated as the number of edges between vertices. A vertex $u$ is considered reachable from vertex $v$ if and only if neither of them is infected, and the number of infected vertices on the path between them does not exceed $M$.

For each possible chosen vertex $s$ ($1 ≤ s ≤ N$), you must calculate the number of vertex pairs $(u, v)$ such that $1 ≤ u < v ≤ N$ and $u$ is reachable from $v$ (and vice versa).

입력

The first line contains three integers: $N$, $R$ and $M$.

The second line contains $N - 1$ integers: $p[2]$, $p[3]$, $\dots$, $p[N]$, the parents of the vertices $2$, $3$, $\dots$,$N$, respectively.

출력

Print $N$ lines with single integer each: $s$-th line should contain required number of pairs when the chosen vertex is $s$.

It's not recommended to use std::endl for outputting newline symbols. Instead, consider using '\n' for better performance.

제한

  • $2 ≤ N ≤ 500\,000$
  • $1 ≤ p[i] < i$ (for each $2 ≤ i ≤ N$)
  • $0 ≤ R ≤ N - 1$
  • $0 ≤ M ≤ 2 \times R + 1$

서브태스크

번호배점제한
120

$N ≤ 300$

214

$R = 0$

315

$M = 2 \times R + 1$

410

$M = 2 \times R − 1$

516

$N ≤ 5\,000$

625

No additional constraints.

예제 입력 1

13 2 2
1 2 3 4 3 6 6 8 2 10 11 1

예제 출력 1

16
4
15
55
66
36
66
55
66
45
55
66
66

The image above corresponds to $s = 2$.

The reachable pairs are: $(1,13)$, $(7,8)$, $(7,9)$, $(8,9)$.

This list doesn't include the pair $(1,2)$ since vertex $2$ is infected. Similarly, the pair $(1,5)$ is absent since the path between $1$ and $5$ has three infected vertices ($2$, $3$ and $4$).

예제 입력 2

3 0 1
1 2

예제 출력 2

1
1
1

채점 및 기타 정보

  • 예제는 채점하지 않는다.