PreVOI 2025 - Pertree

Xem dạng PDF

Gửi bài giải

Điểm: 80,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Một công ty có ~n~ nhân viên, đánh số từ ~1~ đến ~n~. Ngoài nhân viên số ~1~, mỗi nhân viên ~i~ có duy nhất một lãnh đạo trực tiếp ~p_i~. Như vậy, sơ đồ tổ chức của công ty có dạng cây, với gốc là nhân viên ~1~.

Một thứ tự nhận quà được coi là hợp lệ khi mỗi nhân viên trong công ty nhận được đúng một món quà và lãnh đạo ~p_i~ nhận được quà trước nhân viên ~i~.

Theo thứ tự nhận quà đó, người nhận quà thứ ~x~ nhận được món quà có giá trị ~a_x~.

Với mọi ~1 \le x \le n~, hãy in ra tổng giá trị quà mà người thứ ~x~ nhận được trong mọi thứ tự nhận quà hợp lệ. Vì con số này rất lớn, tính theo mod ~10^9+7~.

Input

Dòng đầu tiên ghi số nguyên ~n~.

Dòng thứ ~2~ ghi ~n-1~ số nguyên, trong đó số thứ ~i~ là ~p_{i+1}~.

Dòng thứ ~3~ ghi ~n~ số nguyên, trong đó số thứ ~i~ là ~a_i~.

Output

In ra trên một dòng ~n~ số, trong đó số thứ ~x~ là tổng giá trị quà người thứ ~x~ nhận được trong mọi cách nhận quà hợp lệ, tính theo mod ~10^9+7~.

Scoring

Trong mọi test: ~2 \le n \le 5000, 1 \le p_i < i, 0 \le a_i < 10^9+7~

Subtask Điểm Ràng buộc
1 ~10\%~ ~n \le 10~
2 ~30\%~ ~n \le 350~
3 ~60\%~ ~n \le 5000~

Sample Input 1

4
1 1 2
1 2 3 4

Sample Output 1

3 7 9 11

Sample Input 2

6
1 2 1 3 3
1 7 7 0 1 3

Sample Output 2

10 70 42 36 16 16

Notes

Những thứ tự nhận quà hợp lệ là:

~\{1, 2, 3, 4\}~

~\{1, 2, 4, 3\}~

~\{1, 3, 2, 4\}~

Tổng giá trị quà nhận được của người ~1~ là: ~1+1+1=3~

Tổng giá trị quà nhận được của người ~2~ là: ~2+2+3=7~

Tổng giá trị quà nhận được của người ~3~ là: ~3+4+2=9~

Tổng giá trị quà nhận được của người ~4~ là: ~4+3+4=11~


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.