Tổng GCD Trên Đường Đi Tổ Tiên

Điểm: 7,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho một cây có gốc gồm $n$ đỉnh, gốc tại đỉnh $1$ . Mỗi đỉnh $v$ có một giá trị $x_{v}$ là số nguyên không âm không vượt quá $10^{12}$ .

Đỉnh $u$ được gọi là tổ tiên của đỉnh $v$ nếu $u$ nằm trên đường đi ngắn nhất từ gốc tới $v$ (mỗi đỉnh cũng được coi là tổ tiên của chính nó).

Với cặp $(u, v)$ mà $u$ là tổ tiên của $v$ , giả sử các đỉnh trên đường đi từ $u$ tới $v$ là $u = t_{1}, t_{2}, \dots, t_{k} = v$ . Định nghĩa

$f (u, v) = gcd (x_{t_{1}}, x_{t_{2}}, \dots, x_{t_{k}}) .$

Đặc biệt $f (u, u) = x_{u}$ , và quy ước $gcd (0, y) = gcd (y, 0) = y$ , kể cả $gcd (0, 0) = 0$ .

Yêu cầu: tính

$\sum_{u là tổ tiên của v} f (u, v) (\mod 10^{9} + 7) .$

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a, b$ mô tả một cạnh nối hai đỉnh $a$ và $b$ của cây.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng cần tính, lấy theo modulo $10^{9} + 7$ .

Ràng buộc

$2 \leq n \leq 10^{5}$
$0 \leq x_{i} \leq 10^{12}$
$1 \leq a, b \leq n$ , $a \neq b$
Đồ thị cho trước là một cây liên thông.

Ví dụ

Input	Output	Giải thích
5 4 5 6 0 8 1 2 1 3 1 4 4 5	42	Có $9$ cặp tổ tiên–con cháu (tính cả $(v, v)$ ). Ví dụ $f (1, 5) = gcd (4, 0, 8) = 4$ . Tổng các $f$ bằng $42$ .
7 0 2 3 0 0 0 0 1 2 1 3 2 4 2 5 3 6 3 7	30	Vì $gcd (0, y) = y$ nên các đường đi từ gốc lan toả giá trị khác $0$ xuống các con cháu. Tổng cuối cùng bằng $30$ .

Bình luận

Không có bình luận tại thời điểm này.