Chọn Đội tuyển HSGQG Huế 2024 - Cây
View as PDF
Trong lập trình thi đấu, hai chủ đề thường được nhiều cao thủ ưa thích nhất đó là cây và lý thuyết số, bởi khi nghiên cứu các bài toán khó, thông thường người giải sẽ luôn tìm cách đơn giản hoá bài toán, sau đó sử dụng các kiến thức từ một trong hai lĩnh vực này làm hướng đi để giải quyết những phiên bản "dễ hơn" của bài toán gốc. Sau đây sẽ là một bài toán kết hợp cả hai lĩnh vực dễ và thú vị này.
Cho một cây gồm ~N~ đỉnh, có gốc cố định tại đỉnh ~1~. Mỗi đỉnh ~i~ chứa một số nguyên dương ~a_i~.
Định nghĩa:
~p(u)~ là tích của các số nguyên chứa trong các đỉnh nằm trong cây con gốc ~u~.
~\sigma_0(x)~ là số ước của ~x~.
Bạn được cho ~Q~ truy vấn, mỗi truy vấn là một đỉnh ~u~ (~1 \le u \le n~). Hãy xác định ~\sigma_0(p(u))~ ~mod~ ~10^9 + 7~.
Input
Nhập từ file TREE.INP:
Dòng 1: Hai số nguyên dương ~N, Q~.
Dòng 2: ~N~ số nguyên dương ~a_i~.
Dòng ~3 \rightarrow N + 1~: Mỗi dòng chứa hai số nguyên dương ~u_j, v_j~ thể hiện cạnh thứ của ~j~ cây.
Dòng ~N + 2~: ~Q~ số nguyên thể hiện lần lượt ~Q~ truy vấn.
Output
Xuất ra file TREE.OUT một dòng gồm ~Q~ số nguyên, mỗi số là đáp án của truy vấn tương ứng.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~18\%~ | ~N \le 10^3, Q \le 10^3, 1 \le a_i \le 10^5~ |
| ~2~ | ~12\%~ | ~N \le 10^5, Q \le 5, 1 \le a_i \le 10^5~ |
| ~3~ | ~20\%~ | ~N \le 10^5, Q \le 10^5, 1 \le a_i \le 3~ |
| ~4~ | ~24\%~ | ~N \le 10^5, Q \le 10^5, 1 \le a_i \le 10^5~, cây có dạng đường thẳng |
| ~5~ | ~26\%~ | ~N \le 10^5, Q \le 10^5, 1 \le a_i \le 10^5~ |
Sample Input 1
6 5
2 1 3 4 2 4
1 2
1 3
2 4
2 5
3 6
1 2 3 4 5
Sample Output 1
14 4 6 3 2
Notes
Xét ~u = 2~, ta có:
~p(2) = a_2 \cdot a_4 \cdot a_5 = 1 \cdot 4 \cdot 2 = 8~.
~\sigma_0(p(2)) = \sigma_0(8) = 4~.
Comments
Khi tạo bài tập chọn mục nào để phần Inpout, Output hiện đọc ghi tệp ạ? Mặc định chỉ hiện stdin, stdout
TREE.INP TREE.OUT
khó:))))))
This comment is hidden due to too much negative feedback. Show it anyway.
Ngài Khôi
bài này rất hay
This comment is hidden due to too much negative feedback. Show it anyway.