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:
Ðược add lên bởi Khúc Anh Tuấn
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

Please read the guidelines before commenting.



  • -4
    tminh_hk20  commented on Jan. 11, 2024, 2:47 p.m.

    Note: Đề bài không ràng buộc (a != b) nên khi (a==b) thì kết quả của ta =0.


  • -14
    LeThanhMinh  commented on Dec. 29, 2022, 3:15 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -13
      ANHTUANCBN  commented on March 2, 2023, 11:15 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.