PreVOI 2025 - Pertree
Xem dạng PDFTrong 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