GRASSPLA - Grass Planting


 

Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1 
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!
PROBLEM NAME: grassplant
INPUT FORMAT:
* 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.
SAMPLE INPUT (file grassplant.in):
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
OUTPUT FORMAT:
* Lines 1..???: Each line has the answer to a query, appearing in the
        same order as the queries appear in the input.
SAMPLE OUTPUT (file grassplant.out):
2
1
2

Problem description:

Farmer John has N barren pastures (2 <= N <= 100,000) connected by N-1  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 FORMAT:


* 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.


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


OUTPUT FORMAT:


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


SAMPLE OUTPUT:


2

1

2

 


hide comments
kiwi1995: 2016-07-27 14:20:13

HLD ;)

Hussain Kara Fallah: 2013-09-10 23:53:51

Cool Problem Indeed

[deleted]: 2013-03-03 11:57:35

Ok, got AC

@Gareev I don't understand why I keep getting WA, my code succeeds in all the testcases that I have tried, including the official testcases from the usaco contest. Please, check submission 8822084.

Last edit: 2013-03-06 18:38:10

Added by:Gareev
Date:2012-08-19
Time limit:0.219s-0.438s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:USCAO contests