Gửi bài giải
Điểm:
0,00 (OI)
Giới hạn thời gian:
4.0s
Giới hạn bộ nhớ:
512M
Input:
TREE.INP
Output:
TREE.OUT
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho hai số nguyên dương ~N~ và ~Q~.
Có một cây gồm ~N~ đỉnh, mỗi đỉnh thứ ~i~ ~(1\leq i\leq N)~ cây có một giá trị ~A_i~. Bạn cần trả lời ~Q~ truy vấn có dạng như sau:
- Cho một đỉnh ~X~ ~(1\leq X\leq N)~, hãy tìm đỉnh ~Y~ sao cho giá trị
$$A_Y - A_X - D(X,\ Y)^2$$
là lớn nhất, với ~D(X,\ Y)~ là số cạnh trên đường đi ngắn nhất từ đỉnh ~X~ đến đỉnh ~Y~ trên cây, sau đó đưa ra giá trị lớn nhất đó.
Dữ liệu - Nhập từ tệp văn bản TREE.inp
:
- Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~Q~ ~(1\leq N,\ Q\leq 2\times 10^5)~.
- Dòng tiếp theo gồm ~N~ số nguyên ~A_1,\ A_2,\ \dots,\ A_N~ ~(1\leq A_1,\ A_2,\ \dots,\ A_N\leq 10^9)~.
- ~N - 1~ dòng tiếp theo mỗi dòng gồm hai số nguyên ~U~ và ~V~ mô tả có một cạnh từ đỉnh ~U~ đến đỉnh ~V~ trên cây.
- ~Q~ dòng tiếp theo mỗi dòng gồm một số nguyên ~X~ mô tả các truy vấn ~(1\leq X\leq N)~.
Kết quả - Ghi ra tệp văn bản TREE.out
:
- Gồm ~Q~ dòng chứa kết quả bài toán.
Chấm điểm
Điểm | Ràng buộc bổ sung |
---|---|
~20~ | ~N,\ Q\leq 5000~ |
~22~ | Cây có dạng đường thẳng |
~22~ | Cây có dạng cây nhị phân hoàn hảo |
~36~ | Không có ràng buộc gì thêm |
Ví dụ
Dữ liệu (TREE.inp
)
6 6
10 5 15 6 12 5
1 2
1 3
2 4
2 5
3 6
1
2
3
4
5
6
Kết quả (TREE.out
)
4
6
0
2
0
9
Giải thích
- Với đỉnh ~X = 1~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_1 - D(1,\ 3)^2 = 15 - 10 - 1 = 4~.
- Với đỉnh ~X = 2~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_2 - D(2,\ 3)^2 = 15 - 5 - 4 = 6~.
- Với đỉnh ~X = 3~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_3 - D(3,\ 3)^2 = 15 - 15 - 0 = 0~.
- Với đỉnh ~X = 4~, ta tìm được đỉnh tương ứng là ~Y = 5~, khi đó, giá trị cần tìm là ~A_5 - A_4 - D(4,\ 5)^2 = 12 - 6 - 4 = 2~.
- Với đỉnh ~X = 5~, ta tìm được đỉnh tương ứng là ~Y = 5~, khi đó, giá trị cần tìm là ~A_5 - A_5 - D(5,\ 5)^2 = 12 - 12 - 0 = 0~.
- Với đỉnh ~X = 6~, ta tìm được đỉnh tương ứng là ~Y = 3~, khi đó, giá trị cần tìm là ~A_3 - A_6 - D(6,\ 3)^2 = 15 - 5 - 1 = 9~.
- Dưới đây là hình dạng của cây:
Bình luận