146. Day 3 PH. 樹樹鏈鏈剖剖分分

樹樹鏈鏈剖剖分分

題目敘述

給定一棵樹(樹上沒有環) 有兩種操作:

1. P i j 把第$i$節點到第$j$節點間所有的邊塗色一次
2. Q i j 詢問第$i$節點到第$j$節點間所有的邊共被塗色幾次

輸入說明

第一行有兩個整數$N$, $M$($N,M \leq 200000$)，代表有一棵$N$個點的樹，且有$M$筆操作

接下來有$N-1$行，每行有$a_i$,$b_i$($1 \leq a_i,b_i \leq N$)

代表有一條邊是從$a_i$到$b_i$(點:$1\sim N$)

接著會有$M$行操作(如上)

輸出說明

對操作Q輸出正確答案

範例輸入

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

Judge Setting

run-time limit: 1500 ms
memory limit: 13107100 byte
測資數量: 0