Truy vấn trên cây
View as PDF
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++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
Nếu bạn nào code sai hay bí ý tưởng , có thể tham khảo code của mình rất rõ ràng nhé ! (Mình xin một upvote nếu bạn thấy hay nha (❤️ ω ❤️))
Bạn cày bài khiếp thật
mình làm để ôn luyện bạn
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.