시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 119 | 81 | 70 | 72.165% |
A monochrome tree is a tree in which each vertex is colored either white or black. The score of a monochrome tree is equal to the number of unordered vertex pairs $(u, v)$ such that:
You are given a rooted tree of $n$ vertices whose root vertex is $1$.
For each $k$ from $0$ to $n$ (inclusive), you may color the given tree in such a way that there are exactly $k$ black vertices and $n - k$ white vertices. Among all the possible colorings, we denote the lowest score of a coloring as $c_k$.
Find $c_k$ for all $0 \leq k \leq n$.
The first line contains a single integer $n$, the number of vertices in the given tree. ($1 \leq n \leq 2 \times 10^5$).
The $i$-th line of the following $n-1$ lines contain a single integer $p_{i+1}$ ($1 \leq p_{i+1} \leq n$, $p_{i+1} \neq i+1$), meaning that the parent of vertex $i+1$ is $p_{i+1}$.
On the first and only line, print $n+1$ integers, the $i$-th of which denotes $c_{i-1}$. ($1 \leq i \leq n+1$)
번호 | 배점 | 제한 |
---|---|---|
1 | 20 | $n \leq 20$ |
2 | 20 | $n \leq 500$ |
3 | 60 | No further constraints |
3 1 1
0 0 0 2
3 3 1
0 0 1 3
Vertex $x$ is an ancestor of vertex $y$ $(x \neq y)$ if there is a sequence of vertices $\{x=a_1, a_2, \ldots a_k=y\}$ where $a_i$ is a parent of $a_{i+1}$ ($1 \leq i \leq k-1$).