| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 92 | 7 | 6 | 10.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.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $N ≤ 300$ |
| 2 | 14 | $R = 0$ |
| 3 | 15 | $M = 2 \times R + 1$ |
| 4 | 10 | $M = 2 \times R − 1$ |
| 5 | 16 | $N ≤ 5\,000$ |
| 6 | 25 | No additional constraints. |
13 2 2 1 2 3 4 3 6 6 8 2 10 11 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$).
3 0 1 1 2
1 1 1