P4115 Qtree4

数据范围和 SPOJ 略有不同。

给出一棵边带权的节点数量为 $n$ 的树，初始树上所有节点都是白色。有两种操作： - `C x`，改变节点 $x$ 的颜色，即白变黑，黑变白。 - `A`，询问树中最远的两个白色节点的距离，这两个白色节点可以重合（此时距离为 $0$）。

第一行，输入一个正整数 $n\ (n \le {10}^5$)。 接下来 $n-1$ 行，每行有 $3$ 个整数 $a,b,c$，代表节点 $a$ 和节点 $b$ 之间连一条边权为 $c\ (|c|\le{10}^3)$ 的边。 接下来一行，一个正整数 $q\ (q\le 2\times 10^5)$，表示操作的数量。 接下来 $q$ 行，每行一次操作。

对于每次 `A` 操作，如果树上不存在白点，输出一行一个字符串 `They have disappeared.`，否则输出一行一个整数代表树上最远的两个白色节点的距离。