| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P18QPROE - QUALIFY ROUND 2018 E - LAN TRUYỀN DINH DƯỠNG |
Cho một cây có N đỉnh và gốc tại đỉnh 1. Mỗi nút lá có chức năng tổng hợp chất dinh dưỡng, đồng thời lan truyền năng lượng cũng như các chất dinh dưỡng cho nút cha của nó để thực hiện quá trình tổng hợp. Quá trình lan truyền năng lượng sẽ làm tăng giá trị dinh dưỡng lên 1. Tức là nếu một nút tổng hợp được giá trị dinh dưỡng bằng V, sẽ giúp cho nút cha của nó sẽ tổng hợp được giá trị dinh dưỡng bằng V+1. Nếu một nút cha có nhiều nút con, giá trị dinh dưỡng của nó bằng tổng của giá trị dinh dưỡng của các nút con gửi lên.
Biết rằng mỗi nút lá ban đầu tổng hợp được chất dinh dưỡng có giá trị 1. Nhiệm vụ của bạn là hãy xác định xem mỗi nút của cây tổng hợp được bao nhiêu giá trị dinh dưỡng?
Input
Dòng đầu tiên là số lượng đỉnh N (N ≤ 200 000). Dòng tiếp theo gồm N-1 số nguyên, a[2], a[3], …, a[N] lần lượt là cha của các nút 2, 3, …, N.
Output
In ra N số nguyên, số nguyên thứ i cho biết giá trị dinh dưỡng mà nút i tổng hợp được.
Example
Test 1:
Input: 3
1 1 Output: 5 1 1
Test 2:
Input:
5
1 2 2 4
Output:
13 8 1 3 1
| Được gửi lên bởi: | adm |
| Ngày: | 2018-05-14 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2019-04-02 17:33:21
test 2 tại sao lại ra 13 8 1 3 1 nhỉ? cần ai đó thông não |
|
|
2018-10-29 14:24:51
ad giải thích cho e test 2 với ạ, theo e hiểu thì phải là 8 7 1 3 1 chứ ạ |
