SGAME4

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

vinhntndu

Dạng bài

Đ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:

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.
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)\).