MTREECOL - Color a tree

Giới hạn

• Thời gian: 0.261s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Bob muốn tô màu một cây N nút. Một nút được tô khi và chỉ khi nút cha của nó được tô và chỉ được tô từng nút một. Mỗi nút tô mất 1 đơn vị thời gian (thời điểm bắt đầu là 0).

Nếu Fi là thời điểm kết thúc tô nút i thì chi phí cho tô nút i là Ci x Fi (Ci cho trước).

Ví dụ, nếu tô cây sau theo thứ tự 1, 3, 5, 2, 4 và chi phí Ci cho từng nút là 1, 2, 1, 2 và 4 thì tổng chi phí là 33 và nó là nhỏ nhất.

Cần tính chi phí nhỏ nhất này với một cây bất kỳ.

Input

Gồm nhiều bộ test. Dòng đầu chứa hai số nguyên N và R (1 <= N <= 1000, 1 <= R <= N), với N là số nút và R là chỉ số của nút gốc. Dòng thứ hai chứa N số nguyên C1, C2, .., CN (1 <= Ci <= 500). N-1 dòng tiếp theo mỗi dòng chứa hai số nguyên V1, V2 là cạnh nối hai nút V1 và V2, V1 là cha của V2.

Kết thúc là bộ test có N=R=0 và không cần xử lý.

Sample Input
5 1 
1 2 1 2 4 
1 2 
1 3 
2 4 
3 5 
0 0 

Output

Với mỗi bộ test, in ra chi phí nhỏ nhất cần trả.

Sample output
33

---

• Người up: vdmedragon
• Nguồn bài: Peiking 2004