## QTREE4 - Query on a tree IV

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3...,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.

All the nodes are white initially.

We will ask you to perfrom some instructions of the following form:

• C a : change the color of node a.(from black to white or from white to black)
• A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

### Input

• In the first line there is an integer N (N <= 100000)
• In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
• In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
• In the next Q lines, each line contains an instruction "C a" or "A"

### Output

For each "A" operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".

### Example

```Input:
3
1 2 1
1 3 1
7
A
C 1
A
C 2
A
C 3
A

Output:
2
2
0
They have disappeared.

```

Some new test data cases were added on Apr.29.2008, all the solutions have been rejudged.

hide comments
 Sigma Kappa: 2017-09-08 17:51:02 My update is O(log^n), and queries execute in O(logn), overall it is O(Q log^n). However, it gets TLE. Maybe because in my design the nodes are initially tanned, and I execute n flip-colour operations even before executing the queries... maximum_shot: 2017-06-09 20:04:23 Some hint) Solution O(Q * log(Q) * log(N)) got accept) krist7599555: 2017-05-01 14:42:21 O ((N+Q) log^2 n) is fine but stl make it TLE write your own, so you can get accept :) peehs_moorhsum: 2016-12-24 05:12:50 Why is O(Q*log^2n) TLE? Hibuddy_deathstar: 2016-03-31 21:01:34 getting TLE :( qzqzgfy: 2016-03-01 04:16:04 wowowow chenwenwen: 2014-07-29 13:10:19 Solve it finally. Debugging is so hard. chenwenwen: 2014-07-29 04:51:23 tree split Nitin jaglan: 2014-06-24 13:06:46 what du hahaha: 2014-02-03 15:42:44 how to do

 Added by: Qu Jun Date: 2008-04-25 Time limit: 0.100s-0.646s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET Resource: william