시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 2048 MB | 75 | 36 | 25 | 41.667% |
SWERC organizers want to hold a gastronomic event.
The location of the event is a building with $n$ rooms connected by $n - 1$ corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room.
In each room you have to set up the tasting of a typical Italian dish. You can choose from $n$ typical Italian dishes rated from $1$ to $n$ depending on how good they are ($n$ is the best possible rating). The $n$ dishes have distinct ratings.
You want to assign the $n$ dishes to the $n$ rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that:
If you assign the $n$ dishes optimally, what is the maximum number of pleasing tours?
The first line contains an integer $n$ ($2 ≤ n ≤ 1\,000\,000$) — the number of rooms.
The second line contains $n - 1$ integers $p_2$, $p_3$, $\cdots$, $p_n$ ($1 ≤ p_i < i$). Each $p_i$ indicates that there is a corridor between room $i$ and room $p_i$. It is guaranteed that the building has the property that it is possible to go from any room to any other room.
Print the maximum number of pleasing tours.
5 1 2 2 2
13
Explanation of sample 1.
It is optimal to place the dish with rating $1$ in room $1$, the dish with rating $2$ in room $3$, the dish with rating $3$ in room $2$, the dish with rating $4$ in room $5$ and the dish with rating $5$ in room $4$.
All the $13$ possible pleasing tours are: $(1)$, $(2)$, $(3)$, $(4)$, $(5)$, $(1, 2)$, $(3, 2)$, $(2, 4)$, $(2, 5)$, $(1, 2, 4)$, $(1, 2, 5)$, $(3, 2, 4)$, $(3, 2, 5)$.
There are also other ways to assign the dishes to the rooms so that there are $13$ pleasing tours.
10 1 2 3 4 3 2 7 8 7
47
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2021-2022 K번