(ĐTQG Hà Nội 2024) Bài 4: Trọng số tập đỉnh

Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\), trong đó đỉnh \(1\) là gốc của cây. Tất cả các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(u\) được gọi là tổ tiên của đỉnh \(u\). Mỗi đỉnh đều có hai loại trọng số: đỉnh thứ \(i\) có trọng số của đỉnh là \(a_i\) và trọng số tổ tiên là \(b_i\).

Tổ tiên chung gần nhất của một tập đỉnh là đỉnh chung đầu tiên của các đỉnh khi đi về đỉnh gốc \(1\) (nếu tập hợp gồm \(1\) đỉnh thì tổ tiên chung gần nhất là chính đỉnh đó).

Xét một tập hợp gồm \(k\) \((0 < k \le N)\) đỉnh phân biệt bất kì \(\{u_1, u_2, \dots, u_k\}\). Gọi \(p\) là tổ tiên chung gần nhất của \(k\) đỉnh. Khi đó giá trị của tập đỉnh này được tính bằng công thức:

\[a_{u_1} \times a_{u_2} \times \dots \times a_{u_k} \times b_p.\]

Vậy một cây \(N\) đỉnh sẽ có \(2^N - 1\) tập đỉnh phân biệt.

Yêu cầu. Hãy tính tổng giá trị của tất cả các tập đỉnh có thể tạo ra. Vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho \(10^9 + 7\).

\InputFile

Dòng đầu tiên chứa số nguyên dương \(N\) \((N \le 10^6)\) là số đỉnh của cây.
Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((a_i \le 10^9;\ 1 \le i \le N)\) mô tả trọng số đỉnh của các đỉnh từ đỉnh \(1\) đến đỉnh \(N\).
Dòng thứ ba chứa \(N\) số nguyên dương \(b_1, b_2, \dots, b_N\) \((b_i \le 10^9;\ 1 \le i \le N)\) mô tả trọng số khi nó là tổ tiên của các đỉnh từ đỉnh \(1\) đến đỉnh \(N\).
\(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v\) \((u, v \le N)\) mô tả một cạnh của cây.

\OutputFile

Gồm một số nguyên duy nhất là kết quả của bài toán sau khi lấy phần dư khi chia cho \(10^9 + 7\).

\Examples
\beginexample
\exmp
3
1 1 2
2 1 2
1 2
1 3

\endexample

\Note
Với cây trong ví dụ (gốc \(1\), hai con là \(2\) và \(3\)):

Tập \(\{1\}\) có giá trị: \(2\);
Tập \(\{2\}\) có giá trị: \(1\);
Tập \(\{3\}\) có giá trị: \(4\);
Tập \(\{1, 2\}\) có giá trị: \(2\);
Tập \(\{1, 3\}\) có giá trị: \(4\);
Tập \(\{2, 3\}\) có giá trị: \(4\);
Tập \(\{1, 2, 3\}\) có giá trị: \(4\).

Tổng là \(21\).

\Scoring

(\(20\%\)) \(N \le 15\) và cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), …, đỉnh \(N-1\) nối với đỉnh \(N\);
(\(20\%\)) \(N \le 15\);
(\(20\%\)) Cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), …, đỉnh \(N-1\) nối với đỉnh \(N\);
(\(20\%\)) Mọi trọng số đỉnh của các đỉnh đều là \(1\);
(\(20\%\)) Không có ràng buộc thêm.

\endproblem

Điều hướng chính

Ngôn ngữ

Phím tắt

(ĐTQG Hà Nội 2024) Bài 4: Trọng số tập đỉnh

Bình luận