QTREEV - Một bài tập về cây

Giới hạn
  • Thời gian: 0.1s
  • 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

Cho một đồ thị cây có N đỉnh N-1 cạnh, gốc của cây là đỉnh 1, mỗi đỉnh có một trọng số không âm là A i . Dễ dàng nhận thấy, ngoại trừ đỉnh 1, các đỉnh còn lại đều có một đỉnh cha và nhận nó làm đỉnh con. Từ mảng A người ta tiến hành xây dựng mảng P như sau:

P u =A u nếu như đỉnh u đó không có đỉnh con, ngược lại P u =A u *max(P v1 , P v2 ...P vm ) với v1,v2...vm lần lượt là các đỉnh con trực tiếp có cạnh nối với u. Nhiệm vụ của bạn là tính P 1 .

Input

Dòng 1: Gồm một số nguyên N và M(1≤N≤10 5 , 1≤M≤10 18 ).

Dòng 2: Gồm N số nguyên A 1 ... A N với A i là trọng số của đỉnh thứ i. (A i ≤10 18 ).

N-1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v, thể hiện cạnh nối giữa u và v (1≤u,v≤N).

Output

Một số nguyên duy nhất là P 1 , do kết quả có thể rất lớn nên chỉ cần in ra phần dư cho một số nguyên M

Example 

Input:

3 1000
1 2 3
1 2
1 3

Output:
3

  • Người up: only_love97