#2519. 树上查询 I

树上查询 I

Description

有一棵NN 个节点的树,节点编号为1N1 ~N ,每条边都有一个整数权值。每个节点都有一个颜色:白色或黑 色。将dist(a,b)dist(a , b )定义为从节点aa 到节点bb 路径上的边权值之和。最 初,所有节点都是白色的。执行以下两种操作:① CC aa ,修改节点aa 的 颜色(从黑色到白色或从白色到黑色);②AA,查询相距最远的两个白 色节点的距离dist(a,b)dist(a , b ),节点aa 和节点bb 都必须是白色的(aa 可以 等于bb )。显然,只要有一个白色节点,结果总是非负的。

Format

Input

11行包含一个整数NN105N (N ≤10^5 ),表示节点数。接下来 的N1N -1行,每行都包含三个整数abca、b、c ,表示在aba、b 之间有一条 边,权值为c1000c1000c (-1000≤c ≤1000)。在下一行包含一个整数QQ105Q (Q≤10^5 ),表示指令数。接下来的QQ 行,每行都包含一条指令CC aaAA

Output

对每个指令A都单行输出结果。若树中没有白色节点,则输 出“They have disappeared.”。

Samples

3
1 2 1
1 3 1
7
A
C 1
A
C 2
A
C 3
A
2
2
0
They have disappeared.

来源

SPOJQTREE4