SPOJ QTREE4 - Query on a tree IV

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  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<pair<int,int> >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])<mini){//寻找中心边 
 74         mini=max(sz[u],sz[t[pos].rt]-sz[u]);
 75         mid=id;
 76     }
 77     for(int i=hd[u];i;i=e[i].nxt){
 78         if(i!=(id^1) && !del[i]){
 79             DFS_mid(e[i].v,i);
 80         }
 81     }
 82     return;
 83 }
 84 void pushup(int p){//处理编号为rt的中心边 
 85     t[p].ans=-1;
 86     while(!t[p].q.empty() && (c[t[p].q.top().second]==1)) t[p].q.pop();
 87 //    printf("rt:%d lc:%d rc:%d\n",p,t[p].lc,t[p].rc);
 88     if(!t[p].lc && !t[p].rc){if(!c[t[p].rt])t[p].ans=0;}
 89     else{
 90         int tmp=max(t[t[p].lc].ans,t[t[p].rc].ans);
 91         t[p].ans=max(t[p].ans,tmp);
 92         if(!t[t[p].lc].q.empty() && !t[t[p].rc].q.empty())
 93             t[p].ans=max(t[t[p].lc].q.top().first+t[t[p].rc].q.top().first+t[p].len,t[p].ans);
 94     }
 95     return;
 96 }
 97 void update(int u){
 98     c[u]^=1;
 99     if(c[u])
100         for(int i=tmp[u];i;i=eg[i].nxt){
101             pushup(eg[i].v);
102         }
103     else for(int i=tmp[u];i;i=eg[i].nxt){
104         t[eg[i].v].q.push(make_pair(eg[i].w,u));
105         pushup(eg[i].v);
106     }
107 }
108 void divide(int u,int p){//边分治 
109     t[p].rt=u;
110     pos=p;
111     DFS_S(u,0,0);
112     mid=-1;mini=INF;
113     DFS_mid(u,-1);
114     if(mid>0){
115         del[mid]=1;del[mid^1]=1;
116         int x=e[mid].v,y=e[mid^1].v;//先保存两边的点，否则递归过程中mid变了会导致WA
117         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<n;i++){
130         u=read();v=read();w=read();
131         add1(u,v,w);add1(v,u,w);
132     }
133     mct=1;
134     Rebuild(1,0);
135     memset(tmp,0,sizeof tmp);//初始化原图 
136     mct=1;
137     tot=1;
138     divide(1,tot);    
139     char op[5];
140     m=read();
141     while(m--){
142         scanf("%s",op);
143         if(op[0]==‘A‘){
144             if(t[1].ans>=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 }