QTREEX - Truy vấn trên cây
Giới hạn- Thời gian: 0.854s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một cây gồm N nút đánh số từ 1->N. Các cạnh của cây đánh số từ 1->N-1, mỗi cạnh có trọng số là một số nguyên. Bạn cần viết chương trình thực hiện dãy các lệnh sau:
CHANGE i v => Thay đổi trọng số của cạnh thứ i thành v
NEGATE a b => Đảo dấu trọng số của tất cả các cạnh nằm trên đường đi từ a đến b
QUERY a b => Tìm trọng số lớn nhất của các cạnh nằm trên đường đi từ a đến b
Input
Input là một bộ gồm nhiều test. Dòng đầu của input là số test t ( t<=20 ). Tiếp sau đó là các test.
Mỗi test bắt đầu bằng một dòng trống. Dòng tiếp theo ghi một số N ( N<=10000 ). N-1 dòng tiếp theo, mỗi dòng ghi 3 số a, b và c mô tả một cạnh của cây nối a với b và có trọng số là c. Thứ tự của các cạnh chính là thứ tự xuất hiện trong input. Tiếp theo là dãy các lệnh như mô tả ở trên(số lệnh không quá 50000). Cuối mỗi test ghi một từ "DONE".
Dữ liệu vào luôn đảm bảo trọng số của các cạnh ở mỗi thời điểm có giá trị tuyệt đối không vượt quá 10000000.
Output
Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu a = b thì ghi ra 0.
Example
Input: 1 3 1 2 1 2 3 2 QUERY 1 2 CHANGE 1 3 QUERY 1 2 DONE Output: 1 3
- Người up: beo_map
- Nguồn bài: Ðược add lên bởi Khúc Anh Tuấn