Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem S. 108. (May 2016)

S. 108. Andrew and Brian play a certain game on a tree graph having $\displaystyle N$ ($\displaystyle 1\le N\le 100\,000$) vertices. The game consists of $\displaystyle M$ ($\displaystyle 1\le M\le 100\,000$) steps. Each step is one of the following two possibilities.

– Andrew selects two vertices of the tree, and puts one chocolate on every edge of the unique path between the vertices.

– Brian asks for the number of chocolates on a given edge.

The goal is to answer Brian's questions as quickly as possible.

Your program should read the values of $\displaystyle N$ and $\displaystyle M$ from the first line of the standard input, then the tree edges (represented by the integers $\displaystyle u$ and $\displaystyle v$) from the following $\displaystyle N-1$ lines. Then each of the following $\displaystyle M$ lines starts with either a letter P or Q, followed by a pair of integers $\displaystyle u, v$. This last pair denotes a pair of vertices. Letter P'' means that Andrew has put one chocolate on every edge of the unique path between the vertices $\displaystyle (u, v)$. Letter Q'' means that Brian has asked for the number of chocolates on the edge $\displaystyle (u, v)$. Your program should write the answer to Brian's questions in the successive lines of the standard output.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program with a short documentation—also describing which developer environment to use for compiling the source—should be submitted in a compressed file s108.zip.

(10 pont)

Deadline expired on June 10, 2016.

### Statistics:

 8 students sent a solution. 10 points: Gáspár Attila. 9 points: Janzer Orsolya Lili, Németh 123 Balázs, Noszály Áron. 8 points: 2 students. 3 points: 1 student. 1 point: 1 student.

Problems in Information Technology of KöMaL, May 2016