TLEOJ Contest #15 - Tree GCD - TLEOJ: TLE Online Judge

TLEOJ Contest #15 - Tree GCD

Điểm: 1300 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: TREEGCD.inp

Output: TREEGCD.out

Tác giả:

VilleClaude

Dạng bài

Cho $1$ cây có $n$ đỉnh, các đinh được đánh số từ $1$ đến $n$ . Đỉnh thứ $i$ có trọng số là $w_i$ . Gọi $d(x,y,z)$ là số cạnh ít nhất để liên thông $3$ đỉnh $x,y,z$ $(1\le x<y<z\le n)$ . Gọi $g(x,y,z)$ là số lượng ước nguyên tố của $gcd(w_x,w_y,w_z)$ .
Yêu cầu: Hãy tính tổng tất cả các giá trị $g(x,y,z)$ $\times$ $d(x,y,z)$ với mọi $x,y,z$ thỏa mãn $1\le x<y<z\le n$ .

Input, Output và Subtasks

Input: (TREEGCD.INP)

Dòng đầu tiên gồm $1$ số nguyên dương $n$ ( $1\le n\le 2.10^5$ ).
Dòng tiếp theo gồm $n$ số nguyên dương $w_1,w_2,...,w_n$ ( $1\le w_i\le 2.10^5$ ).
Tiếp theo là $n-1$ dòng mô tả cây, mỗi dòng gồm $2$ nguyên dương $u,v$ ( $1\le u,v\le n,u\neq v$ ) cho biết có cạnh nối giữa đỉnh $u$ và đỉnh $v$ . Đảm bảo dữ liệu vào luôn là cây.

Output: (TREEGCD.OUT)

Gồm $1$ số nguyên là đáp án của bài toán. Kết quả có thể rất lớn nên hãy chia lấy dư cho $10^9+7$ .

Subtasks

Subtask 1: Đảm bảo $n\le 200$ . ( $20$ % số điểm)
Subtask 2: Đảm bảo $n\le 2.10^5,w_i\le 2$ . ( $30$ % số điểm)
Subtask 3: Không có ràng buộc gì thêm. ( $50$ % số điểm)

Sample

Input (TREEGCD.INP)

Output (TREEGCD.OUT)

Bình luận

Không có bình luận nào.