题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1095
括号序列。。
orz岛娘http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-%E6%8D%89%E8%BF%B7%E8%97%8F/
#include<cstring> #include<iostream> #include<algorithm> #include<cstdio> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 200500 #define inf int(1e9) #define ll long long #define mm 1000000007 using namespace std; int head[maxn],dfn[maxn*3],a[maxn*3],c[maxn],tot,n,q; struct data{int obj,pre; }e[maxn*2]; struct seg{ int l,r,l1,l2,r1,r2,c1,c2,s; void ini(int x){ l=r=x; if (a[x]==-2) c2=1; if (a[x]==-5) c1=1; if (a[x]>0&&c[a[x]]==1) l1=l2=r1=r2=0; else l1=l2=r1=r2=-inf; } } t[maxn*3*4]; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y){ e[++tot].obj=y; e[tot].pre=head[x]; head[x]=tot; } void dfs(int u,int f){ a[++tot]=-2; a[++tot]=u; dfn[u]=tot; for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (v!=f) dfs(v,u); } a[++tot]=-5; } inline seg merge(seg s1,seg s2){ seg s; s.l=s1.l,s.r=s2.r; int a=s1.c1,b=s1.c2,c=s2.c1,d=s2.c2; if (c>b) s.c1=a+c-b,s.c2=d; if (c<=b) s.c1=a,s.c2=d+b-c; s.s=max(s1.s,s2.s); s.s=max(s.s,s1.r1+s2.l2); s.s=max(s.s,s1.r2+s2.l1); s.r1=max(s2.r1,max(s1.r1-c+d,s1.r2+c+d)); s.r2=max(s2.r2,s1.r2+c-d); s.l1=max(s1.l1,max(s2.l1+a-b,s2.l2+a+b)); s.l2=max(s1.l2,s2.l2-a+b); return s; } void change(int i,int x){ int l=t[i].l,r=t[i].r,mid=(l+r)/2; if (l==r) {t[i].ini(x); return;} if (x<=mid) change(i*2,x); else change(i*2+1,x); t[i]=merge(t[i*2],t[i*2+1]); } void build(int i,int l,int r){ if (l==r){ t[i].l=l; t[i].r=r; t[i].ini(l); return; } int mid=(l+r)/2; build(i*2,l,mid); build(i*2+1,mid+1,r); t[i]=merge(t[i*2],t[i*2+1]); } int main(){ n=read(); int black=0; rep(i,1,n) c[i]=1,black++; rep(i,1,n-1){ int x=read(),y=read(); insert(x,y); insert(y,x); } dfs(1,0); build(1,1,tot); q=read(); char ch[2]; rep(i,1,q){ scanf("%s",ch); if (ch[0]=='G'){ if (!black) puts("-1"); else if (black==1) puts("0"); else printf("%d ",t[1].s); } else { int x=read(); if (c[x]) black--; else black++; c[x]^=1; change(1,dfn[x]); } } return 0; }