Submit solution
Points:
1.13 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho một cây gồm ~N~ nút đánh số từ ~1 \rightarrow N~. Các cạnh của cây đánh số từ ~1 \rightarrow 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~ ~\rightarrow~ Thay đổi trọng số của cạnh thứ ~i~ thành ~v~
- NEGATE ~a~ ~b~ ~\rightarrow~ Đả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~ ~\rightarrow~ 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 \leq 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 \leq 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á ~10\,000\,000~.
Output
- Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu ~a = b~ thì ghi ra ~0~.
Sample Input
1
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
Sample Output
1
3
Comments
Sol từ cowboy coder
ngon