Bedao Regular Contest 01 - HOGWARTS

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đào có ~m~ cây cầu được xây sẵn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_j~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

  • ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~

  • ~D~ ~j~ có tác dụng xóa đi cây cầu thứ ~j~ nối hai hòn đảo ~u_j~ và ~v_j~

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input

  • Dòng thứ nhất chứa ba số nguyên ~n~, ~m~, ~q~ ~(n, m, q \leq 3*10^{5})~
  • Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1, w_2, ..., w_n~ ~(w_i \leq 10^9)~
  • ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_j~ và ~v_j~
  • ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~

Output

  • ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Sample Input

6 6 8
8 2 1 8 3 7 
4 3
4 2
3 4
6 1
4 3
4 3
D 5
D 4
C 5 8
D 3
C 2 8
C 5 1
C 6 1
D 2

Sample Output

15
11
11
11
17
17
17
9

Comments

Please read the guidelines before commenting.


There are no comments at the moment.