Network

Xem dạng PDF
Gửi bài giải
Điểm: 1,03 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
PreVNOI 2013 Day 1, Problem 3, Nguyen Tuan Anh
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Những ngày nghỉ tại NTU là thời gian để ANHNT ngẫm nghĩ về các cấu trúc mạng máy tính. Mạng mà ANHNT đang nghiên cứu gồm có ~n~ máy tính đánh số từ ~1~ tới ~n~ và ~n - 1~ dây cáp mạng đánh số từ ~1~ tới ~n - 1~. Dây cáp thứ ~i~ nối giữa hai máy tính ~u_i~, ~v_i~ và cho phép truyền tin giữa hai máy này theo cả hai chiều với độ tin cậy là ~w_i~.

Ta nói máy ~s~ và máy ~t~ có thể truyền tin cho nhau nếu như tồn tại đường truyền tin là dãy ~s = x_1~, ~x_2~, ..., ~x_k = t~ sao cho các máy ~x_1, x_2~, ..., ~x_k~ hoàn toàn phân biệt và giữa máy ~x_i~ và ~x_{i + 1}~ có cáp nối trực tiếp ~(\forall i = 1~, ~2~, ..., ~k - 1)~. Mạng đảm bảo việc truyền tin giữa hai máy bất kỳ.

ANHNT đang loay hoay trả lời ~m~ câu hỏi, mỗi câu hỏi thuộc một trong hai dạng:

  • ~P~ ~a~ ~b~ ~c~: Cần cho biết trên đường truyền tin từ máy ~a~ tới máy ~b~ có bao nhiêu cáp nối mà độ tin cậy nhỏ hơn hoặc bằng ~c~
  • ~T~ ~k~ ~c~: Cần cho biết nếu cắt bỏ dây cáp thứ ~k~ thì trong số những dây cáp có thể truyền tin từ máy ~v_k~, có bao nhiêu cáp nối mà độ tin cậy nhỏ hơn hoặc bằng ~c~

Yêu cầu: Cho mạng máy tính, và danh sách các câu hỏi, hãy giúp ANHNT trả lời tất cả các câu hỏi đó.

Input

  • Dòng ~1~ chứa hai số nguyên dương ~n~, ~m \leq 10^{5}~

  • ~n - 1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u_i~, ~v_i~, ~w_i~ ~(\forall i: 1 \leq u_i~, ~v_i \leq n~; ~w_i \leq 10^9)~

  • ~m~ dòng tiếp theo mỗi dòng ghi một câu hỏi, ký tự đầu dòng ~\in \{P, T\}~ cho biết loại câu hỏi

    • Nếu ký tự đầu dòng là ~P~, tiếp theo là ba số nguyên dương ~a~, ~b~, ~c~ ứng với dạng câu hỏi ~P~ ~a~ ~b~ ~c~ ~(1 \leq a~, ~b \leq n~; ~c \leq 10^{9})~
    • Nếu ký tự đầu dòng là ~T~, tiếp theo là hai số nguyên dương ~k~, ~c~ ứng với dạng câu hỏi ~T~ ~k~ ~c~ ~(1 \leq k < n~; ~c \leq 10^{9})~

Output

  • Ghi ra ~m~ dòng, mỗi dòng ghi một số nguyên duy nhất là đáp số cho một câu hỏi theo đúng thứ tự đã cho.

Sample Input

6 3
1 2 1
2 3 2
2 4 4
4 5 3
4 6 5
P 1 5 3
T 1 4
T 5 1

Sample Output

2
3
0

Note

Đề gốc PREVOI 2013:

Bình luận

Hãy đọc nội quy trước khi bình luận.