SQRT Cup 2025 - Vòng loại thứ hai - Cây

Xem dạng PDF

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:

png


Bình luận

Hãy đọc nội quy trước khi bình luận.


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