DISTRIBUTE - Trạm thu phí
View as PDFMorioh là một thành phố lớn gồm N điểm du lịch và ~N – 1~ con đường nối từ điểm du lịch này sang điểm du lịch khác sao cho từ một điểm du lịch bất kì có thể đi được tới tất cả các điểm còn lại.
Josuke được ngài thị trưởng giao trách nhiệm đặt các trạm thu phí trên mỗi con đường sao cho chi phí của mỗi con đường là một số nguyên dương và số lượng con đường có chi phí là 1 phải nhỏ nhất có thể. Josuke rất thích số ~K~ nên tích tất cả các chi phí trên mỗi con đường phải bằng ~K~. Vì ~K~ là một số rất lớn nên ~K~ sẽ được biểu diễn sang tích ~M~ thừa số nguyên tố ~p_1~, ~p_2~, … ~p_M~. (~p_1~ ⋅ ~p_2~ ⋅ … ~p_M~ = K). Chi phí của đường đi từ điểm du lịch u đến điểm du lịch v là tổng tất cả các chi phí trên đường đi từ ~u~ đến ~v~. Gọi d(i, j) là chi phí để đi từ i đến j. Hãy giúp Josuke phân phối các chi phí sao cho tổng chi phí để di chuyển giữa các điểm du lịch phải lớn nhất có thể. Hay nói cách khác : ~\sum_{n=i}^{n-1}~~\sum_{n=j}^{n} d(i,j)~ phải lớn nhất có thể.
Dữ liệu vào:
- Dòng đầu tiên gồm số N (N ≤ ~10^5~)
- N – 1 dòng sau, dòng thứ i gồm 2 số ~u_i~ và ~v_i~ (1 ≤ ~u_i~ , ~v_i~ ≤ n), tức là có đường đi từ điểm du lịch ~u_i~ đến điểm du lịch ~v_i~
- Dòng tiếp theo gôm số M (M ≤ 6 ⋅ ~10^4~)
- Dòng tiếp theo gồm M số ~p_1~, ~p_2~, … ~p_M~ (2 ≤ ~p_i~ ≤ 6 ⋅ ~10^4~)
Kết quả gồm:
- 1 dòng là kết quả tìm được. Vì kết quả rất lớn nên hãy lấy kết quả mod ~1000000007~.
Ví dụ:
INPUT 1
4
1 2
2 3
3 4
2
2 2
OUTPUT 1
17
INPUT 2
7
6 1
2 3
4 6
7 3
5 1
3 6
4
7 5 13 3
OUPUT 2
286
Comments
This comment is hidden due to too much negative feedback. Show it anyway.