SP14924 GRAFFTOL - King Graffs Tolls

King Graff, the ruler of the land of Feerie, feels that he is not quite rich enough. As such, he would like to impose travel tolls on his people! After all, why should they get to walk around his kingdom for free? Feerie consists of $ N $ ( $ 1 \leq N \leq 10^5 $ ) towns (numbered $ 1..N $ ), and $ N-1 $ roads. The $ i $ th road runs between distinct towns $ A_i $ and $ B_i $ , in both directions. Every pair of towns is connected by exactly one path of connected roads. Currently, all travel is free, but King Graff is interested in charging for passage through certain towns. He is planning to have a meeting with the royal computer scientest - that would be you. The meeting will last $ M $ ( $ 1 \leq M \leq 10^5 $ ) minutes, and in the $ i $ th minute, one of two things will occur, described by $ T_i $ . If $ T_i= $ "T", Graff will proclaim that town $ X_i $ shall henceforth cost $ Y_i $ ( $ 0 \leq Y_i \leq 10^9 $ ) dollars to pass through, and you'll update the map accordingly. Otherwise, if $ T_i= $ "Q", he will ask you how much a trip from town $ X_i $ to a different town $ Y_i $ would currently cost a commoner, in order to gauge the effectiveness of his tolls - and you had better answer quickly! Note that neither the starting nor the ending town's tolls are included in a trip's cost, as they are not passed through. Note also that a town's toll may be modified by Graff mutiple times throughout the meeting, in which case the most recent modification at any point will stand.

First line: 1 integer, $ N $ Next $ N-1 $ lines: 2 integers, $ A_i $ and $ B_i $ , for $ i = 1..N-1 $ Next line: 1 integer, $ M $ Next $ M $ lines: 1 character, $ T_i $ , and 2 integers, $ X_i $ and $ Y_i $ , for $ i = 1..M $

$ X $ lines (where $ X $ is the number of questions asked by King Graff): 1 integer, the cost of the $ i $ th trip asked for (in dollars), for $ i = 1..X $