P4115 Qtree4

The Constraints here differ slightly from SPOJ.

You are given a tree with $n$ nodes, where each edge has a weight. Initially, all nodes are white. There are two types of operations: - `C x`: toggle the color of node $x$; white becomes black, and black becomes white. - `A`: query the distance between the farthest two white nodes in the tree. These two white nodes may coincide (in which case the distance is $0$).

The first line contains a positive integer $n$ ($n \le 10^5$). Each of the next $n-1$ lines contains three integers $a$, $b$, $c$, representing an edge between nodes $a$ and $b$ with weight $c$ ($|c| \le 10^3$). The next line contains a positive integer $q$ ($q \le 2\times 10^5$), the number of operations. Each of the next $q$ lines contains one operation.

For each `A` operation, if there are no white nodes in the tree, output a line with the string `They have disappeared.`. Otherwise, output a line with one integer, the distance between the farthest two white nodes in the tree.

Translated by ChatGPT 5