Trò con bò
Xem dạng PDF
Farmer John và em đang chăn bò ở trên trang trại của mình. Vì thấy chán nên Farmer John đã ra một trò chơi cho người em.
Hiện tại, trên trang có ~N~ cái chuồng đang trống và độc lập nhau. Vì là quản trò nên Farmer John sẽ ra ~K~ lượt ra hiệu lệnh và có ba loại hiệu lệnh sau:
join ~X~ ~Y~: kết nối chuồng thứ ~X~ và chuồng thứ ~Y~ lại với nhau.
add ~X~ ~V~: cho chuồng thứ ~X~ và những chuồng được kết nối với chuồng ~X~ thêm ~V~ ~(V\le100)~ con bò. Hai chuồng ~X~ và ~Y~ kết nối với nhau nếu như từ chuồng ~X~ ta có thể đi đến chuồng ~Y~ qua một số chuồng trung gian được kết nối với nhau.
get ~X~: Farmer John hỏi em rằng chuồng thứ ~X~ có bao nhiêu con bò
Vì em của Farmer John còn non trẻ nên đã nhò bạn làm bài này. Bạn hãy giúp đỡ nhé.
Input
Dòng đầu tiền gồm hai số ~N~ và ~K~ ~(N\le10^5,K\le5\times10^5)~.
~K~ dòng tiếp theo là lệnh của Farmer John.
Output
Gồm một số dòng là kết quả của các lệnh get, mỗi lệnh trên một dòng.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~30\%~ | ~N,K\le5000~ |
| ~2~ | ~30\%~ | mọi truy vấn join đều có ~v=u+1~ |
| ~3~ | ~40\%~ | Không có ràng buộc gì thêm |
Sample Input 1
4 10
join 1 2
add 1 100
join 2 3
add 1 50
join 3 4
add 1 25
get 1
get 2
get 3
get 4
Sample Output 1
175
175
75
25
Bình luận
add X V là thêm V con bò cho tất cả hay mỗi chuồng liên thông thêm V con bò vậy
toàn làm trò con bò
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.