bzoj1095 線段樹括号序列

題目分析

首先%%% 島姐的講解

然後%%% hzwer的代碼

最後%%% 樹王的幫助

好吧，寫寫我的感悟。

括号序列與距離

首先我們對于一棵美麗的樹，可以生成一個先序周遊的括号序列，左括号表示到達該店，右括号表示離開該點。例如下圖這棵美麗的樹，可以生成一個這樣的序列：（1（2（3）（5））（4）（6（7）））

這個序列有什麼用呢？兩個點之間的距離，就是它們之間括号序列去掉可以比對的括号後的括号數。這是為什麼呢？是因為兩個點之間的路徑相當于遇到左括号向下走，遇到右括号向下走，比對的括号即走了來回沒有必要。

例如上圖3和4節點，之間的括号為）（））（，去掉比對的得到））（，即他們之間的距離為3.

括号序列與線段樹

好了，那麼我們要求的是最遠的兩個黑點之間的距離dis（左區間dis，右區間dis，橫跨左右區間的dis）。

先不考慮黑點。

既然這樣，那麼我們當然要用線段樹維護某兩個點之間的“去掉比對的括号後的括号數”，設括号序列裡的某一段S有c1個右括号，c2個左括号。線上段樹裡S被拆成左邊是S1右邊是S2，a1=S1.c，b1=S1.c2，a2=S2.c1，b2=S2.c2，a=S.c1，b=S.c2。合并S1與S2的時候因為要去掉比對的括号，是以：

當b1>a2時，a=a1,b=b1+b2-a2;

否則，a=a1+a2-b1,b=b2;

這樣就可以用線段樹維護c1和c2了，鼓掌！！！！撒花！！！！

黑白點資訊的維護

%了hzwer代碼後，我發現可以額外開一個數組來表示每一個點是黑是白，更改方式可以看代碼啦，我就不講了，還是不難的。

是以我們主要就是講updata函數。

首先，根據上面的式子可以發現，a+b=a1+b2+|b1-a2|=max((a1-b1)+(a2+b2),(a1+b1)+(b2-a2));這麼一來，我們就知道我們要維護的東西了（因為維護dis的方法）：

l1:是該區間一段字首，在這個字首後面就是一個黑點，a+b。

l2:是該區間一段字首，在這個字首後面就是一個黑點，b-a。

r1:是該區間一段字尾，在這個字尾前面就是一個黑點，a+b。

r2:是該區間一段字尾，在這個字尾前面就是一個黑點，a-b。

那麼：S.dis=max(S1.dis,S2.dis,S1.r1+S2.l2,S1.r2+S2.l1);

好的，那麼我們怎麼維護l1,l2,r1,r2呢？

由于a+b=max((a1-b1)+(a2+b2),(a1+b1)+(b2-a2)),是以：

S.l1=max(S1.l1，S2.l1+a1-b1，S2.l2+a1+b1); （左區間，橫跨左右區間）

S.r1=max(S2.r1，S1.r2+a2+b2，S1.r1+b2-a1);

然後很容易得到：

S.l2=max(S2.r2，S1.r2+a2-b2);

S.r2=max(S1.l1，S2.l2+b1-a1);

因為寫的比較快，如有誤請指出并看代碼。

好了，這個問題解決了。

代碼

有一些内容是抄的hzwer的…

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
const int N=;
int n,tot,now,black,m,inf=;
int c[N],h[N],ne[N<<],to[N<<],v[N*],pos[N];
struct node{int c1,c2,l1,l2,r1,r2,dis;}tr[N*];
//c1:右括号，c2：左括号
void add(int x,int y){to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x,int las){
    v[++now]=-,v[++now]=x,pos[x]=now;
    for(int i=h[x];i;i=ne[i])
        if(to[i]!=las)dfs(to[i],x);
    v[++now]=-;
}
void getdata(int x,int i){
    tr[i].dis=-inf,tr[i].c1=tr[i].c2=;
    if(v[x]==-)tr[i].c2=;
    if(v[x]==-)tr[i].c1=;
    if(v[x]>&&c[v[x]])tr[i].l1=tr[i].l2=tr[i].r1=tr[i].r2=;
    else tr[i].l1=tr[i].l2=tr[i].r1=tr[i].r2=-inf;
}
void up(int i){
    int l=(i<<),r=(i<<)|;
    int a1=tr[l].c1,b1=tr[l].c2,a2=tr[r].c1,b2=tr[r].c2;
    tr[i].dis=max(tr[l].r1+tr[r].l2,tr[l].r2+tr[r].l1);
    tr[i].dis=max(tr[l].dis,max(tr[i].dis,tr[r].dis));
    if(b1>a2)tr[i].c1=a1,tr[i].c2=b2+b1-a2;
    else tr[i].c1=a1+a2-b1,tr[i].c2=b2;
    tr[i].r1=max(tr[r].r1,max(tr[l].r2+a2+b2,tr[l].r1+b2-a2));
    tr[i].r2=max(tr[r].r2,tr[l].r2+a2-b2);
    tr[i].l1=max(tr[l].l1,max(tr[r].l1+a1-b1,tr[r].l2+a1+b1));
    tr[i].l2=max(tr[l].l2,tr[r].l2+b1-a1);
}
void build(int s,int t,int i){
    if(s==t){getdata(s,i);return;}
    int mid=(s+t)>>;
    build(s,mid,i<<),build(mid+,t,(i<<)|);
    up(i);
}
void chan(int x,int s,int t,int i){
    if(s==t){getdata(s,i);return;}
    int mid=(s+t)>>;
    if(x<=mid)chan(x,s,mid,i<<);
    else chan(x,mid+,t,(i<<)|);
    up(i);
}
int main(){
    int i,x,y;char ch[];
    scanf("%d",&n),black=n;
    for(i=;i<=n;++i)c[i]=;
    for(i=;i<n;++i)scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(,-),build(,now,);
    scanf("%d",&m);
    for(i=;i<=m;++i){
        scanf("%s",ch);
        if(ch[]=='C'){
            scanf("%d",&x);
            if(c[x])--black;
            else ++black;
            c[x]^=;
            chan(pos[x],,now,);//注意這裡是pos[x]！！！
        }
        else {
            if(!black)printf("-1\n");
            else if(black==)printf("0\n");
            else printf("%d\n",tr[].dis);
        }
    }
    return ;
}