GRASSPLA - Grass Planting

# 题目描述 约翰有 N 个牧场，编号为 1 到 N。它们之间有 N − 1 条道路，每条道路连接两个牧场。通过这些道路，所有牧场都是连通的。 刚开始的时候，所有道路都是光秃秃的，没有青草。约翰会在一些道路上批量种草。每次开始种草的时候，约翰会选择一个牧场作为起点，一个牧场作为终点，找到从起点到终点的最短路径，在这条路径上所有的道路上分别种下一棵新的青草。 贝西在监督约翰的工作，她迫不及待地想知道每条道路上已经有多少青草了。约翰的工作总是被贝西打断，他不胜其烦，所以请你来帮忙回答贝西的问题。约翰的工作和贝西的询问是穿插进行的，输入数据将会依次出现 M 个事件，以字符 P 开头的事件表示约翰在一条路径上种植了青草，以字符Q 开头的事件表示贝西在查询一条道路上有多少青草。 # 输入格式 第一行：两个整数 N 和 M， 2 ≤ N ≤ 10^6; 1 ≤ M ≤ 10^6 第二行到第 N 行：第 i + 1 行有两个整数 Ui 和 Vi，表示第 i 条道路连接的两个牧场编号，1 ≤ Ui， Vi ≤ N 第 N + 1 行到第 N + M 行：每行首先由一个大写字母： 如果是 P，随后会有两个整数 A 和 B，表示约翰在从 A 通向 B 的每条道路上都新种了一棵青草， 1 ≤ A， B ≤ N。 如果是 Q，随后会有两个整数 A 和 B，表示贝西查询一条道路上的青草数量， A 和 B 是这条道路的两个端点， 1 ≤ A， B ≤ N，保证输入数据中存在一条 A 到 B 的道路。 # 输出格式 对每个查询请求，输出该条道路上青草的数量，以换行符分隔

\* Line 1: Two space-separated integers N and M \* Lines 2..N: Two space-separated integers describing the endpoints of a road. \* Lines N+1..N+M: Line i+1 describes step i. The first character of the line is either P or Q, which describes whether or not FJ is planting grass or simply querying. This is followed by two space-separated integers A\_i and B\_i (1 <= A\_i, B\_i <= N) which describe FJ's action or query.

\* Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.

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