Đề: http://vnoi.info/problems/show/QTREEX/

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

Chúc bạn may mắn.

Hướng dẫn: 

http://simizer.com/tCy

Nhức đầu, chóng mặt, mắc ngủ ?????????????????????

Sinh test fix rồi ngủ :P

Code :

http://simizer.com/A6V