题解 P2056 【[ZJOI2007]捉迷藏 】

· · 题解

安利一发我的blog

神仙般的操作……

膜拜岛娘的思路和hzwer的代码……

我们先假设有以上这么一棵树（图丑勿介）

进行先序遍历，得到[A[B[E][F[H][I]]][C][D[G]]]

再把所有字母去掉[ [ [ ] [ [ ] [ ] ] ] [ ] [ [ ] ] ]

这就是这一棵树的括号编码（本质是dfs得到的）

花了这么大功夫找，但这玩意儿到底有什么用呢？

我们考虑两个节点，E和G

取出他们之间的那段括号编码] [ [ ] [ ] ] ] [ ] [ [

再将所有匹配的括号去掉，得到] ] [ [

我们看到了两个]和两个[

再回到树上，我们发现E向上走两步，再向下走两步就到达了G

于是发现括号序列可以很方便地维护点与点之间的距离

能不能进一步优化呢？

我们发现，对于距离而言，匹配的括号是没有任何意义的

而且，由于距离只需要记录数字，所以维护括号也是没有意义的，只要有编码就行，可以用一个二元组(a,b)来描述它，表示有a个]和b个[

所以，如果有两个点P和Q，如果介于P和Q之间的括号编码表示为(a,b)，则P和Q在树上的距离就是a+b

是不是很方便啊~(≧▽≦)/~啦啦啦

但是现在问题又来了，怎么维护编码呢？

如果可以通过左边一半的信息和右边一半的信息，从而得到整段编码的信息，就可以用我们熟悉的线段树来维护了

我们可以进行如下的分析

考虑对于两段括号编码s1(a,b)和s2(c,d)，他们合并起来可以得到s(x,y)

注意到s1和s2合并起来时会产生min(b,c)的匹配括号，合并后他们会被抵消掉

于是

当 b<c 时第一段 [ 就被消完了，两段 ] 连在一起，例如：

] ] [ [ + ] ] ] [ [ = ] ] ] [ [

当 b>=c 时第二段 ] 就被消完了，两段 [ 连在一起，例如：

] ] [ [ [ + ] ] [ [ = ] ] [ [ [

于是就得到了几个十分有用的结论

当 b<c 时，(x,y) = (a-b+c,d)

当 b>=c 时，(x,y) = (a,b-c+d)

于是就可以用线段树维护整棵树的括号编码~(≧▽≦)/~啦啦啦

题目所要求维护的，是max{a+b|s'(a,b)是s的一个子串，且s'位于两黑点之间}，我们将这个值表示为dis(s)

我们先根据上面的两条结论，得到几个推论

①x+y=a+d+|b-c|=max((a+b-c+d),(a-b+c+d))

②x-y=a-b+c-d

③y-x=b-a+d-c

由①式我们可以发现，要维护dis(s)，要维护四个值a+b,d-c,a-b,d+c

又为了保证s'在两个黑点之间，所以要加上一些限制

于是定义出如下四个参数

rightplus:max(a+b),s'是s的一个前缀且s紧接在一个黑点之后

rightminus:max(a-b),s'是s的一个前缀且s紧接在一个黑点之后

leftplus:max(a+b),s'是s的一个后缀且一个黑点紧接在s之后

leftminus:max(b-a),s'是s的一个后缀且一个黑点紧接在s之后

于是我们就可以用左右两半的状态转移到一整段的状态啦

还是考虑s(x,y),s1(a,b),s2(c,d)

(x,y)=b<c?(a-b+c,d):(a,b-c+d) dis(s)=max(dis(s1),dis(s2),rightplus(s1)+leftminus(s2),rightminus(s1)+leftplus(s2))

（把四个参数的值带入上面的等式很容易发现这是正确的）

然后再来考虑如何求出四个参数呢？

rightplus(s)=max(rightplus(s1)-c+d,rightminus(s1)+c+d,rightplus(s2)) rightminus(s)=max(rightminus(s1)+c-d,rightminus(s2)) leftplus(s)=max(leftplus(s2)-b+a,left_minus(s1)+b+a,leftplus(s1)) leftminus(s)=max(leftminus(s2)+b-a,leftminus(s1))

然后就可以用线段树处理整个括号编码了

实际实现的时候还有一些小细节要注意

我们为了实现更方便，最好还是在编码时加入括号

对于底层结点，如果对应字符是一个括号或者一个白点，那 么right_plus、right_minus、left_plus、left_minus、dis 的值就都是 -inf；如果对应字符是一个黑点，那么 right_plus、right_minus、left_plus、left_minus 都是 0，dis 是-inf。

具体细节可以参见代码，注解比较详细（主要是因为自己照着打了一遍也不太看得懂代码……）

// luogu-judger-enable-o2
//minamoto
#include<bits/stdc++.h>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getchar()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getchar());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
int ver[N<<1],Next[N<<1],head[N];
int v[N*3],pos[N],c[N];
int n,q,cnt,tot,black;
struct seg{
    int l,r,l1,l2,r1,r2,c1,c2,dis;
    void init(int x){
        dis=-inf;
        c1=c2=0;
        if(v[x]==-1) c2=1;
        if(v[x]==-2) c1=1;
        /*c2为失配左括号，c1为失配右括号 
        为左括号，c2=1；为右括号，c1=1*/
        if(v[x]>0&&c[v[x]]) l1=l2=r1=r2=0;
        else l1=l2=r1=r2=-inf;
        /*为黑点，l_plus,l_minus,r_plus,r_minus全为0 
        为白点或括号，全为1*/
    }
}a[N*12];
inline int max(int a,int b,int c){return max(a,max(b,c));}
void add(int u,int v){
    ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
    ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
}
void dfs(int u,int fa){
    v[++cnt]=-1;
    v[++cnt]=u;
    pos[u]=cnt;
    for(int i=head[u];i;i=Next[i])
    if(ver[i]!=fa) dfs(ver[i],u);
    v[++cnt]=-2;
    /*进入加左括号，离开加右括号*/
}
inline void merge(seg &s,seg s1,seg s2){
    /*r1=max(a+b),r2=max(a-b){s1(a,b)是s前缀且s1紧接在一个黑点之后}
    l1=max(a+b),l2=max(b-a){s2(a,b)是s后缀且s2紧接在一个黑点之前}*/
    int a=s1.c1,b=s1.c2,c=s2.c1,d=s2.c2;
    s.dis=max(s1.dis,s2.dis);
    s.dis=max(s.dis,s1.r1+s2.l2,s1.r2+s2.l1);
    /*s.dis=max(s1.dis,s2.dis,a1+b1-a2+b2,a1-b1+a2+b2)*/ 
    b<c?(s.c1=a-b+c,s.c2=d):(s.c1=a,s.c2=b-c+d);
    s.r1=max(s2.r1,s1.r1-c+d,s1.r2+c+d);
    /*a+b=max(a1-b1+a2+b2,a1+b1+b2-a2)*/
    s.r2=max(s2.r2,s1.r2+c-d);
    /*a-b=a1-b1+a2-b2*/
    s.l1=max(s1.l1,s2.l1-b+a,s2.l2+b+a);
    /*同62行*/
    s.l2=max(s1.l2,s2.l2+b-a);
    /*b-a=b2-a2+b1-a1*/
}
void build(int p,int l,int r){
    a[p].l=l,a[p].r=r;
    if(l==r){
        a[p].init(l);
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    merge(a[p],a[p<<1],a[p<<1|1]);
}
void modify(int p,int x){
    int l=a[p].l,r=a[p].r;
    if(l==r){a[p].init(l);return;}
    int mid=(l+r)>>1;
    if(x<=mid) modify(p<<1,x);
    else modify(p<<1|1,x);
    merge(a[p],a[p<<1],a[p<<1|1]);
}
int main(){
    //freopen("testdata.in","r",stdin);
    black=n=read();
    for(int i=1;i<=n;++i) c[i]=1;
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v);
    }
    dfs(1,0);
    build(1,1,cnt);
    q=read();
    while(q--){
        char s[10];
        scanf("%s",s);
        if(s[0]=='C'){
            int x=read();
            if(c[x]) --black;
            else ++black;
            c[x]^=1;
            modify(1,pos[x]);
        }
        else{
            if(!black) puts("-1");
            else if(black==1) puts("0");
            else printf("%d\n",a[1].dis);
        }
    }
    return 0;
}