Trạm độc lập (Independent Stations)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một hệ thống gồm $N$ trạm được nối với nhau bởi $N-1$ tuyến cáp hai chiều, tạo thành một cây.

Trạm thứ $i$ có mức lợi ích $A_i$ nếu được kích hoạt.

Do nhiễu tín hiệu, hai trạm được nối trực tiếp bởi một tuyến cáp không được phép cùng được kích hoạt.

Ta cần chọn một tập hợp các trạm sao cho không có hai trạm được chọn nào kề nhau.

Giá trị của một phương án bằng tổng mức lợi ích của các trạm được chọn.

Hãy xác định:

• tổng lợi ích lớn nhất có thể đạt được;
• số phương án chọn trạm khác nhau đạt được tổng lợi ích lớn nhất đó.

Hai phương án được xem là khác nhau nếu tập chỉ số các trạm được chọn khác nhau.

Số phương án có thể rất lớn, vì vậy chỉ cần tính số phương án theo modulo $1\,000\,000\,007$.

Input

• Dòng đầu chứa số nguyên $N$ — số lượng trạm.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$ — mức lợi ích của các trạm.
• $N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$, mô tả một tuyến cáp hai chiều nối trực tiếp trạm $u$ với trạm $v$.

Output

In ra hai số nguyên:

• tổng lợi ích lớn nhất có thể đạt được;
• số phương án đạt được tổng lợi ích đó, lấy modulo $1\,000\,000\,007$.

Subtask

• Subtask 1 — 20%: $1 \le N \le 24$; $1 \le A_i \le 10^9$. Time Limit: 1,0 giây.
• Subtask 3 — 80%: $1 \le N \le 2\cdot10^5$; $1 \le A_i \le 10^9$. Time Limit: 2,0 giây.

Ví dụ

Ví dụ 1

Input

5
5 1 4 3 2
1 2
1 3
3 4
3 5

Output

10 1

Giải thích

Có thể chọn các trạm $1$, $4$ và $5$.

Không có hai trạm nào trong ba trạm này được nối trực tiếp với nhau, nên đây là một phương án hợp lệ.

Tổng lợi ích là

Không có phương án hợp lệ nào có tổng lợi ích lớn hơn $10$, và chỉ có đúng một phương án đạt giá trị này.

Vì vậy kết quả là 10 1.

Ví dụ 2

Input

3
2 1 1
1 2
1 3

Output

2 2

Giải thích

Có hai phương án đạt tổng lợi ích bằng $2$:

• chọn trạm $1$;
• chọn hai trạm $2$ và $3$.

Hai trạm $2$ và $3$ không được nối trực tiếp với nhau nên có thể cùng được chọn.

Không có phương án nào đạt tổng lợi ích lớn hơn $2$, vì vậy tổng lợi ích tối ưu là $2$ và có $2$ phương án đạt được giá trị đó.