3402. [USACO11DEC] Grass Planting G

【题目描述】

给出一棵有 $n$ 个节点的树，有 $m$ 个如下所示的操作：

将两个节点之间的路径上的边的权值均加一。

查询两个节点之间的那一条边的权值，保证两个节点直接相连。

初始边权均为 $0$。

【输入格式】

第一行两个整数 $n,m$，含义如上。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。

接下来 $m$ 行，每行格式为 `op u v`，$op=P$ 代表第一个操作，$op=Q$ 代表第二个操作。

【输出格式】

若干行。对于每个查询操作，输出一行整数，代表查询的答案。

【样例 1 输入】

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 

【样例 1 输出】

2 
1 
2 

【数据范围】

对于 $100\%$ 的数据，$2\le n\le 10^5$，$1\le m\le 10^5$。