Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

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à Ai. 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:

Pu=Au nếu như đỉnh u đó không có đỉnh con, ngược lại Pu=Au*max(Pv1, Pv2...Pvm) 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 P1.

Input

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

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

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à P1, 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

Được gửi lên bởi:Thương
Ngày:2014-09-07
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU PERL6 PYPY RUST SED

hide comments
2017-08-03 17:47:47
Tham khảo:
http://cowboycoder.tech/spoj/spoj-qtreev-mot-bai-tap-ve-cay
2016-11-15 14:27:49
bạn ở dưới cho xin cái thuật toán với chứng minh đc không ạ :3
2016-11-15 14:21:40
code ds kề sub gần chục sub...dùng vector thì AC...
2014-12-14 08:46:05 FO3 Ronaldinho Gaucho XI !!!!
M là j mà bằng 1000 vậy các bác ???
2014-12-03 19:15:54 livw
o(1)
2014-09-13 16:57:27 Anh Duc Le
cin lại nhanh hơn scanf :v
2014-09-10 08:00:02 Nhung anh sao dem
mình nghĩ cái TL 0.1s nó k hay ho cho lắm.
P/s: h ms nhận ra PS bài này cùng tên vs mình :D
ps: sau khi ac cậu sẽ thấy 0,1s là quá nhiều =)))))))))

Last edit: 2014-09-10 10:09:27
2014-09-10 07:54:13 VOJ Team
Mình nghĩ PS nên sửa tên bài lại cho phù hợp một chút :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.