Truy vấn trên cây (Query on a tree)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho cây có trọng số trên cạnh. Hỗ trợ thay đổi trọng số của một cạnh và truy vấn trọng số cạnh lớn nhất trên đường đi giữa hai đỉnh. Bản PHOJ bỏ số lượng test ở đầu vào; mỗi file chứa đúng một cây và kết thúc dãy lệnh bằng DONE.

Dữ liệu vào

Dòng đầu chứa $n$. Tiếp theo $n-1$ dòng, dòng thứ $i$ chứa u v w cho cạnh số $i$. Sau đó là các lệnh CHANGE i x, QUERY a b; chuỗi lệnh kết thúc bằng DONE.

Kết quả

Với mỗi lệnh QUERY, in trọng số cạnh lớn nhất trên đường đi.

Subtask

Subtask 1 (20%)

• Kích thước cây và số thao tác không vượt 20.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• Kích thước cây và số thao tác không vượt 2000.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n\le10000$, trọng số cạnh không vượt $10^6$; bản PHOJ dùng một test case.

Ví dụ

Input

1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
QUERY 1 1
DONE

Output

0
0
0
0
0
0
0
0
0
0
0
0
0
0

Giải thích

Ví dụ được xử lý đúng theo thứ tự các thao tác. Các truy vấn chỉ quan sát trạng thái hiện tại sau toàn bộ cập nhật đứng trước chúng; kết quả in ra tương ứng với định nghĩa ở phần Đề bài.