GRASSPLA  Grass Planting
Problem description
Farmer John has N barren pastures (2 <= N <= 100,000) connected by N1 bidirectional roads, such that there is exactly one path between any two pastures. Bessie, a cow who loves her grazing time, often complains about how there is no grass on the roads between pastures. Farmer John loves Bessie very much, and today he is finally going to plant grass on the roads. He will do so using a procedure consisting of M steps (1 <= M <= 100,000).
At each step one of two things will happen:
 FJ will choose two pastures, and plant a patch of grass along each road in between the two pastures, or,
 Bessie will ask about how many patches of grass on a particular road, and Farmer John must answer her question.
Farmer John is a very poor counter  help him answer Bessie's questions!
Input
* Line 1: Two spaceseparated integers N and M
* Lines 2..N: Two spaceseparated 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 spaceseparated integers A_i and B_i (1 <= A_i, B_i <= N) which describe FJ's action or query.
Output
* Lines 1..???: Each line has the answer to a query, appearing in the same order as the queries appear in the input.
Example
SAMPLE 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
SAMPLE OUTPUT
2 1 2
[ Edited by EB ]
Warning: Some input files are broken.
hide comments
webbly:
20240222 05:45:28
"Some input files are broken."


[Rampage] Blue.Mary:
20220802 01:35:43
No need to use HLD at all, just simple LCA + segment tree is enough. 

cleverxia:
20220801 16:10:30
it is HLD...but why am i re with sigsegv? 

wruperd:
20220714 13:15:00
why RE 

princemishra:
20220711 20:15:18
finally..... :) 

implicit__:
20210906 13:10:57
A good and straightforward problem on (lazy propagation + HLD) 

an09mous:
20200326 12:19:59
Must do problem if you are learning hld 

joe85123:
20190825 16:33:47
basic HLD with lazy propagation, but the implementation is really a pain.... 

kiwi1995:
20160727 14:20:13
HLD ;) 

Hussain Kara Fallah:
20130910 23:53:51
Cool Problem Indeed 
Added by:  Gareev 
Date:  20120819 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  USCAO contests 