Problem : 151 - 塗色問題

Problem Statistics

Solved Member: 10　　Submission: 80　　User Tried: 11

Statement:

有 n 個點，用雙向的道路連通，使得任意兩點之間都恰好有一條路徑可以互相往來。起初道路是沒有任何顏色的，由於道路空空的非常無趣，所以HH決定心血來潮對道路塗色。

HH有 m 次操作，每次可以把點 i 到點 j 之間的道路塗色，或者詢問點 i 到點 j 的路途中每條道路總共被塗色幾次。請你回答他的問題！

Input:Output:

第 1 行有一個數字 n(n ≤ 100000)以及 m(m ≤ 100000)，代表點數以及詢問數。
後面的 n-1 行每行有兩個數字 a,b，代表有一條雙向道路連接 a,b 兩點。
接下來的 m 行，每行由一個字元 a 以及兩個數字 b,c組成，若 a 為 'P'，代表 HH 要將 b 到 c 之間的所有道路塗色。若 a 為 'Q'，代表 HH 想詢問 b 到 c 之間的道路總共被塗色幾次。

對於每一筆 'Q' 開頭的詢問，請輸出一行數字，代表當時有幾條路已經被著色了。

Sample Input:Sample Output:

4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

2
1
2

HINT:

對於第一筆詢問：
道路(1,4)被塗過1次，道路(4,2)被塗過1次，道路(4,3)被塗過2次。
故回答2。

Source:

USACO 2011 Dec. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2000ms	131072kb
1	2000ms	131072kb	7
2	2000ms	131072kb	7
3	2000ms	131072kb	7
4	2000ms	131072kb	7
5	2000ms	131072kb	8
6	2000ms	131072kb	8
7	2000ms	131072kb	8
8	2000ms	131072kb	8
9	2000ms	131072kb	8
10	2000ms	131072kb	8
11	2000ms	131072kb	8
12	2000ms	131072kb	8
13	2000ms	131072kb	8