TLEOJ Contest #15 - Tree GCD

View as PDF

Submit solution

Points: 1300 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: TREEGCD.inp
Output: TREEGCD.out

Author:
Problem type

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)
4
1 2 2 4
1 2
1 3
1 4
Output (TREEGCD.OUT)
3

Comments

There are no comments at the moment.