Caves and Tunnels#5285
After landing on the surface of Mars, scientists discovered a strange system of caves connected by tunnels. They began researching it using remote-controlled robots. It turned out that there exists exactly one route between every pair of caves. However, the scientists faced a particular problem: sometimes faint explosions occur in the caves. These explosions cause the emission of radioactive isotopes and increase the radiation level in the cave. Unfortunately, robots do not withstand radiation well. Nevertheless, for research purposes, they must travel from one cave to another. Therefore, the scientists placed sensors in every cave to monitor radiation levels. Now, whenever the robots are moved, the scientists want to know the maximum radiation level the robot will have to face during its relocation.
So they have asked you to write a program that will solve their problem.
The first line contains one integer (1 \leq N \leq 100\,000) — the number of caves. The next N-1 lines describe the tunnels. Each of these lines contains two integers a_i and b_i (1 \leq a_i, b_i \leq N), specifying the numbers of the caves connected by the corresponding tunnel. The following line contains an integer (1 \leq Q \leq 100\,000), representing the number of queries. Each of the next lines contains a query in the format "C U V", where is a single character, either 'I' or 'G', indicating the type of query (quotes for clarity only).
If the query type is 'I', the radiation level in the -th cave (1 \leq U \leq N) is increased by (0 \leq V \leq 10\,000). If the query type is 'G', your program must output the maximum radiation level on the path between caves numbered and (1 \leq U, V \leq N) after all the previous increases ('I' queries). Initially, the radiation level in all caves is and it never decreases over time (because the half-life of the isotopes is much greater than the observation period).
For each 'G' query, output one line containing only the maximum radiation level on the specified path.
Example 1