SP14924 GRAFFTOL - King Graffs Tolls

Feerie 的国王 Graff 觉得金库还不够充盈，于是决定对臣民的出行收取通行费！毕竟，他们不能总是免费在他的王国中穿行。 Feerie 包含 $N$ 个城镇（编号从 $1$ 到 $N$），并用 $N-1$ 条道路连接。第 $i$ 条道路连接了两个不同的城镇 $A_i$ 和 $B_i$，道路是双向的。任意两个城镇之间恰好有一条独特的路径相连。目前，所有的通行都是免费的，但 Graff 国王希望对在某些城镇的通行收费。 即将与皇家计算机科学家（也就是你）进行一场会议，会议预计持续 $M$ 分钟（$1 \leq M \leq 10^5$）。在第 $i$ 分钟，有两种可能的事件会发生，由 $T_i$ 表示。如果 $T_i = \text{T}$，Graff 将宣布城镇 $X_i$ 从此起收 $Y_i$ 美元的通行费，你需要相应地更新地图。否则，如果 $T_i = \text{Q}$，他会询问你，从城镇 $X_i$ 到另外一个城镇 $Y_i$ 的旅行目前需要多少费用，以此来衡量通行费的效果——你的回答必须迅速而准确！需注意，起点和终点城镇的通行费不计入旅行费用，因为这些城镇并不经过。此外，通行费可能会被多次修改，每次以最新修改为准。

- 第一行输入一个整数 $N$，表示城镇数量。 - 接下来 $N-1$ 行，每行输入两个整数 $A_i$ 和 $B_i$，表示城镇之间的连接道路。 - 再接下来一行输入一个整数 $M$，表示会议期间的事件数量。 - 随后的 $M$ 行，每行由一个字符 $T_i$ 和两个整数 $X_i$ 和 $Y_i$ 组成，描述具体事件。

- 对于每一个由国王提问的事件，用 $X$ 行表示，从第 $i$ 个问题中计算出的旅行费用（单位：美元）。

- $1 \leq N \leq 10^5$ - 每条道路最多收费 $10^9$ 美元 **本翻译由 AI 自动生成**