BZOJ1095: [ZJOI2007]Hide 捉迷藏

Evan课件上讲了括号序列。。。
发现很厉害的样子
想了一个晚上才搞出来

线段树维护就好了
岛娘：
http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-%E6%8D%89%E8%BF%B7%E8%97%8F/

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

char c;
inline void read(int &a)
{
    a=0;do c=getchar();while(c<'0'||c>'9');
    while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();
}

struct Seg
{
     int l,r;
     int lplus,rplus,ldif,rdif;
     int d;
     int a,b;     
     bool Light;
}T[3000001];
int dfsn[1000001];
int cnt;
int pla[1000001];

struct Chain
{
    Chain *next;
    int u;
    Chain(){next=NULL;}
}*Head[100001];

void dfs(int u,int fa)
{
    dfsn[++cnt]=-2;
    dfsn[++cnt]=u;
    pla[u]=cnt;
    for(Chain *tp=Head[u];tp;tp=tp->next)
      if(tp->u!=fa)dfs(tp->u,u);    
    dfsn[++cnt]=-1;
}
const
   int INF=1<<28;
inline void empty(int place)
{T[place].rplus=T[place].lplus=T[place].rdif=T[place].ldif=T[place].d=-INF;T[place].Light=false;}
inline void Light(int place)
{T[place].rplus=T[place].lplus=T[place].rdif=T[place].ldif=T[place].d=0;T[place].Light=true;}
void Build(int place,int l,int r) 
{ 
  T[place].l=l,T[place].r=r;
   if(l^r)
  {
   int lc=place<<1,rc=lc|1,mid=(l+r)>>1;
      Build(lc,l,mid);
      Build(rc,mid+1,r);
    T[place].lplus=max(max(T[lc].a-T[lc].b+T[rc].lplus,
                          T[lc].a+T[lc].b+T[rc].ldif),T[lc].lplus);
   T[place].rplus=max(max(T[rc].a+T[rc].b+T[lc].rdif,
                          T[rc].b-T[rc].a+T[lc].rplus),T[rc].rplus); 
   T[place].ldif=max(T[lc].ldif,T[lc].b-T[lc].a+T[rc].ldif);
   T[place].rdif=max(T[rc].rdif,T[rc].a-T[rc].b+T[lc].rdif); 
   T[place].d=max(T[lc].d,max(T[rc].d,max(T[lc].rdif+T[rc].lplus,T[rc].ldif+T[lc].rplus)));
   int tp=T[rc].a-T[lc].b;
   T[place].a=T[lc].a+(tp<0?0:tp);
   T[place].b=T[rc].b+(tp<0?-tp:0);
    return;
   }
   if(dfsn[l]==-1)
      T[place].a=1,T[place].b=0,empty(place);
   else if(dfsn[l]==-2)
      T[place].a=0,T[place].b=1,empty(place);
   else
      T[place].a=0,T[place].b=0,Light(place); 
}


inline void Query(){printf("%d\n",T[1].d==-INF?-1:T[1].d);}
void Modify(int place,int l)
{
   if(!(T[place].l^T[place].r))
    { 
    T[place].Light? empty(place):Light(place);return ;}
   int lc=place<<1,rc=place<<1|1;
   if(l<=T[lc].r)
      Modify(lc,l);
    else
      Modify(rc,l);
   T[place].lplus=max(max(T[lc].a-T[lc].b+T[rc].lplus,
                          T[lc].a+T[lc].b+T[rc].ldif),T[lc].lplus);
   T[place].rplus=max(max(T[rc].a+T[rc].b+T[lc].rdif,
                          T[rc].b-T[rc].a+T[lc].rplus),T[rc].rplus); 
   T[place].ldif=max(T[lc].ldif,T[lc].b-T[lc].a+T[rc].ldif);
   T[place].rdif=max(T[rc].rdif,T[rc].a-T[rc].b+T[lc].rdif); 
   T[place].d=max(T[lc].d,max(T[rc].d,max(T[lc].rdif+T[rc].lplus,T[rc].ldif+T[lc].rplus)));
   int tp=T[rc].a-T[lc].b;
   T[place].a=T[lc].a+(tp<0?0:tp);
   T[place].b=T[rc].b+(tp<0?-tp:0);
}

inline void addside(int a,int b){Chain *tp=new Chain;tp->next=Head[a],Head[a]=tp,tp->u=b;}
int n;
int main()
{
    read(n);
    int i,j,k;
    for(i=1;i<n;i++)
       read(j),read(k),addside(j,k),addside(k,j);
    dfs(1,1);
    Build(1,1,cnt);
    int Q;
    read(Q);
    while(Q--)
    {
        do c=getchar();while(c!='G'&&c!='C');
        if(c=='C')
         {
            read(j);Modify(1,pla[j]);
         }
         else if(c=='G')
          {
            Query();
          }
    }

    return 0;
}