Cây Đũa Phép Cơm Nguội

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Trong thế giới phù thủy, có $N$ phù thủy, mỗi người sở hữu một lượng sức mạnh phép thuật $p_{i}$ . Các phù thủy có thể tạo ra liên kết thần phục - những kết nối ma thuật cho phép sức mạnh truyền qua giữa họ.

Cây Đũa Phép Cơm Nguội (Elder Wand), một bảo vật huyền thoại, có khả năng khuếch đại sức mạnh phép thuật truyền qua các chuỗi thần phục. Khi một phù thủy cầm Cây Đũa Phép và truyền sức mạnh đến một phù thủy khác qua chuỗi liên kết, tổng sức mạnh được khuếch đại bằng tổng sức mạnh của tất cả phù thủy trên đường đi (bao gồm cả hai đầu).

Ban đầu, không có liên kết thần phục nào tồn tại. Bạn cần xử lý $Q$ thao tác:

1 u v - Tạo liên kết thần phục giữa phù thủy $u$ và phù thủy $v$ . Đảm bảo $u$ và $v$ thuộc hai nhóm khác nhau.
2 u v - Phá hủy liên kết trực tiếp giữa phù thủy $u$ và $v$ . Đảm bảo liên kết này tồn tại.
3 u v - Tính tổng sức mạnh trên đường đi từ phù thủy $u$ đến phù thủy $v$ . Đảm bảo $u$ và $v$ thuộc cùng một nhóm.
4 u x - Sức mạnh của phù thủy $u$ thay đổi thành $x$ .

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $Q$ .
Dòng thứ hai chứa $N$ số nguyên $p_{1}, p_{2}, \dots, p_{N}$ - sức mạnh ban đầu của các phù thủy.
$Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác theo định dạng trên.

Dữ liệu ra

Với mỗi thao tác loại 3, in ra tổng sức mạnh trên đường đi trên một dòng.

Ràng buộc

$1 \leq N, Q \leq 10^{5}$
$1 \leq p_{i}, x \leq 10^{9}$
$1 \leq u, v \leq N$
Các thao tác luôn hợp lệ (xem mô tả ở trên)
Tổng sức mạnh trên đường đi có thể vượt quá $2^{31} - 1$

Ví dụ

Input	Output	Giải thích
5 7 1 2 3 4 5 1 1 2 1 2 3 3 1 3 1 4 5 3 4 5 2 2 3 3 1 2	6 9 3	Liên kết 1-2, rồi 2-3. Truy vấn đường 1→2→3: tổng = 1+2+3 = 6. Liên kết 4-5. Truy vấn đường 4→5: tổng = 4+5 = 9. Phá liên kết 2-3. Truy vấn đường 1→2: tổng = 1+2 = 3.
3 5 10 20 30 1 1 2 1 2 3 3 1 3 4 2 50 3 1 3	60 90	Liên kết 1-2, rồi 2-3. Truy vấn đường 1→2→3: tổng = 10+20+30 = 60. Cập nhật sức mạnh phù thủy 2 thành 50. Truy vấn lại đường 1→2→3: tổng = 10+50+30 = 90.

Bình luận

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