SGAME4

Xem PDF

Điểm: 500 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nông dân V.H.A có \(N\) khu vườn để chăn nuôi chú gà SPyofgame. Các khu vườn được kết nối với nhau bằng \(N-1\) con đường hai chiều, tức là chỉ có đúng một đường đi giữa hai khu vườn (giàu mà keo đây mà). Vì là một con gà béo tham lam nên SPyofgame đã đòi hỏi trên đường các con đường luôn phải có đồ ăn cho nó. Vì thế, V.H.A đã phải thực hiện các công việc sau:

  1. P x y: V.H.A sẽ chọn ra hai khu vườn và bỏ 1 nồi thóc dọc theo con đường nối hai khu vườn.
  2. Q x y: V.H.A sẽ phải trả lời trên đoạn đường nối hai khu vườn có bao nhiêu nồi thóc.

Input:

  • Dòng đầu tiên chứa hai số nguyên \(N, M (1 \leq M \leq 100000, 2 \leq N \leq 100000).\)
  • \(N-1\) dòng tiếp theo, mỗi dòng là hai số nguyên thể hiện hai đầu nối của một con đường.
  • \(M\) dòng cuối cùng, mỗi dòng là một truy vấn theo cấu trúc P x y hoặc Q x y \((1 \leq x,y \leq N)\).

Output:

  • Mỗi dòng là câu trả lời cho mỗi truy vấn Q theo thứ tự.

Example

Test 1

Input
3 3
1 2
2 3
P 1 3
Q 2 3
Q 1 3
Output
1
2

Bình luận


  • 0
    tuanlinh    8:15 a.m. 24 Tháng 7, 2020

    trong test VD đặt 1 nồi trên đường 1-3 nhưng khi trả lời truy vấn lại có 2 cái ?


    • 0
      vinhntndu    8:31 a.m. 24 Tháng 7, 2020

      ngẫm kĩ đề bạn ơi


      • 1
        vinhntndu    8:31 a.m. 24 Tháng 7, 2020

        đặt trên đường đi từ 1 đến 3, tức là 1->2 rồi 2->3 nên đoạn đường 2-3 có 1, 1-3 có 2


        • 0
          hhoangcpascal    11:41 a.m. 24 Tháng 7, 2020 đã chỉnh sửa

          Mà đề phải là \(N-1\) dòng tiếp theo chứ :V Có \(N-1\) cạnh chứ mấy


          • 0
            vinhntndu    11:52 a.m. 24 Tháng 7, 2020

            á nhầm đề 🙂

        4 bình luận nữa