Công ty

Một công ty vận hành theo mô hình phân cấp rõ ràng: mỗi nhân viên (ngoại trừ Giám đốc điều hành) đều có một cấp trên trực tiếp, tạo thành một cấu trúc cây gốc với CEO là người số 1.

Mỗi nhân viên được gán một chỉ số ảnh hưởng cá nhân -- đại diện cho năng lực, trách nhiệm, hoặc độ tín nhiệm của người đó. Khi đánh giá tác động trong hệ thống báo cáo, công ty muốn phân tích xem trong tất cả các tuyến báo cáo ngược từ một nhân viên đến các cấp trên của họ, ảnh hưởng "yếu nhất" (thấp nhất) trên mỗi tuyến là bao nhiêu.

Cụ thể, với mỗi nhân viên $x$, bạn cần:

• Xét tất cả các cấp trên trực tiếp hoặc gián tiếp \(y\) của họ;
• Với mỗi cặp \((x, y)\) sao cho \(y\) là cấp trên của \(x\), hãy tính giá trị nhỏ nhất của các chỉ số ảnh hưởng trên đường đi từ \(x\) đến \(y\);
• Sau đó, cộng tất cả các giá trị nhỏ nhất này lại để có kết quả cuối cùng cho \(x\).

Input

• Dòng đầu tiên là số nguyên \(n\) -- tổng số nhân viên trong công ty \((n \leq 10^5)\).
• Dòng tiếp theo gồm \(n - 1\) số nguyên, mỗi số ở vị trí \(i\) cho biết người quản lý trực tiếp của nhân viên số \(i+1\).
• Dòng tiếp theo gồm \(n\) số nguyên, số thứ \(i\) là \(a_{i}\) - chỉ số ảnh hưởng của nhân viên số \(i\) \((0 \leq a_{i} \leq 10^9)\)

Output

• In ra \(n\) số nguyên. Số thứ \(i\) là tổng của các giá trị ảnh hưởng thấp nhất trên tất cả các tuyến báo cáo từ nhân viên \(i\) đến các cấp trên của họ (bao gồm cả bản thân họ).

Example

7
1 1 2 2 3 3
3 2 3 1 4 5 9

3 4 6 3 8 11 15 

Scoring

• Subtask 1 (30% số điểm): \(n \leq 100\).
• Subtask 2 (20% số điểm): \(n \leq 1000\).
• Subtask 3 (20% số điểm): Mỗi nhân viên chỉ có tối đa \(1\) cấp trên và \(1\) cấp dưới (cây có dạng đường thẳng).
• Subtask 4 (30% số điểm): \(n \leq 10^5\).