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:31 2 11 3 17AC 1AC 2AC 3AOutput:220They have disappeared.

 

给出一棵边带权的树，初始树上所有节点都是白色。

有两种操作：

C x，改变节点x的颜色，即白变黑，黑变白

A，询问树中最远的两个白色节点的距离，这两个白色节点可以重合(此时距离为0)。

 

树 边分治

试着写了边分治，花式WAWAWA，最后不得已还是开启了标准代码比对。

这么复杂的东西估计过几天就忘，悲伤

果然加上虚点以后内存占用超大啊……边要开到mxn<<4

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 using namespace std;  7 const int INF=1e8;  8 const int mxn=200010;  9 int read(){ 10     int x=0,f=1;char ch=getchar(); 11     while(ch<'0' || ch>'9'){
   if(ch=='-')f=-1;ch=getchar();} 12     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();} 13     return x*f; 14 } 15 struct edge{ 16     int v,nxt;int w; 17 }e[mxn<<4],eg[mxn<<2]; 18 int hd[mxn],mct=1; 19 int tmp[mxn]; 20 void add_edge(int u,int v,int w){
   //虚点图  21     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].w=w;hd[u]=mct;return; 22 } 23 void add1(int u,int v,int w){
   //原图  24     eg[++mct].v=v;eg[mct].nxt=tmp[u];eg[mct].w=w;tmp[u]=mct;return; 25 } 26 int n,m; 27 int c[mxn];//颜色 28  29 void Rebuild(int u,int fa){
   //建立添加了虚点的新图  30     int ff=0; 31     for(int i=tmp[u];i;i=eg[i].nxt){
   //tmp存原图边  32         int v=eg[i].v; 33         if(v==fa)continue; 34         if(!ff){ 35             add_edge(u,v,eg[i].w); 36             add_edge(v,u,eg[i].w); 37             ff=u; 38             Rebuild(v,u); 39         } 40         else{ 41             c[++n]=1;//添加虚点 42             add_edge(ff,n,0);add_edge(n,ff,0); 43             add_edge(n,v,eg[i].w); 44             add_edge(v,n,eg[i].w); 45             ff=n; 46             Rebuild(v,u); 47         } 48     } 49     return; 50 } 51 struct node{ 52     int rt,len,ans; 53     int lc,rc; 54     priority_queue
          
           
             >q; 55 }t[mxn<<2]; 56 bool del[mxn<<2]; 57 int pos,mini,mid; 58 int sz[mxn],tot=0; 59 void DFS_S(int u,int d,int fa){ //计算子树各结点距离 60 add1(u,pos,d);//用原图的空间来存边分治的点边关系 61 //从当前结点向"管辖它的边代表的结点"连边 62 if(!c[u]) t[pos].q.push(make_pair(d,u)); 63 sz[u]=1; 64 for(int i=hd[u];i;i=e[i].nxt){ 65 int v=e[i].v; 66 if(v==fa || del[i])continue; 67 DFS_S(v,d+e[i].w,u); 68 sz[u]+=sz[v]; 69 } 70 return; 71 } 72 void DFS_mid(int u,int id){ 73 if(max(sz[u],sz[t[pos].rt]-sz[u])
            
             0){115 del[mid]=1;del[mid^1]=1;116 int x=e[mid].v,y=e[mid^1].v;//先保存两边的点，否则递归过程中mid变了会导致WA117 t[p].len=e[mid].w;118 t[p].lc=++tot;119 t[p].rc=++tot;120 divide(x,t[p].lc);121 divide(y,t[p].rc);122 }123 pushup(p);124 }125 int main(){126 int i,j,u,v,w;127 n=read();128 mct=6*n;129 for(i=1;i
             
              =0)145 printf("%d\n",t[1].ans);146 else printf("They have disappeared.\n");147 }148 else{149 w=read();150 update(w);151 }152 }153 return 0;154 }