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.|

HB_KT2B3 - Tạo mảng P

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ố 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 của u. Nhiệm vụ của bạn là tính P1.

Input

  • Dòng 1: Gồm một số nguyên N, số đỉnh của đồ thị (1<=N<=105).
  • Dòng 2: Gồm N số nguyên A1 ... AN với Ai là trọng số của đỉnh thứ i. (1<=Ai<=109).
  • N-1 dòng tiếp theo, mỗi dòng gồm hai số nguyên u và v, tức là đỉnh u là cha đỉnh 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 109+7.

Example

Input:

3

1 2 3

1 2

1 3

Output: 3

Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-09-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC MAWK BC C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG DART ELIXIR FANTOM FORTH GRV JULIA KTLN OBJC OCT PAS-FPC PROLOG PYPY3 R RACKET CHICKEN SQLITE SWIFT UNLAMBDA
Nguồn bài:Bạn Nguyễn Khánh Việt

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.