bzoj 4817

LCT好题

首先我们考虑实际询问的是什么：

从LCT的角度考虑，如果我们认为一开始树上每一条边都是虚边，把一次涂色看作一次access操作，那么询问的实际就是两个节点间的虚边数量+1和子树中的最大虚边数量！

这种问题显然树上容斥，如果设$dis_{i}$表示$i$到根节点需要经过多少虚边，那么答案显然是$dis_{x}+dis_{y}-2dis_{LCA(x,y)}+1$

那么我们实际只是在维护这个$dis_{i}$

怎么维护?

我们注意到，虚实边的转化对应着access操作，因此我们肯定考虑access中进行维护

注意到在每次access的时候，实际对应着三步操作：

第一步：将节点旋转到根

第二步：将节点与右子树之间的边由实边断为虚边

第三步：将节点与原先节点之间的边由虚边变为实边

那么实边变为虚边对应着虚边数量增加，虚边变为实边对应着虚边数量减少

由于这棵树的形态不变，我们考虑直接用线段树维护dfs序，这样就支持了单点查询$dis$和查询子树中最大的$dis$

在修改的时候，考虑到每次access操作的过程，每一次虚实边的变化实际影响的是一棵子树

而这棵子树的根就是在splay上右子树中最靠左的那个点！

因此我们找到这个根，更新即可，区间修改，单点查询+区间查询即可

贴代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define rt1 rt<<1

#define rt2 (rt<<1)|1

using namespace std;

struct Seg_tree

{

    int lazy,maxv;

}tree[400005];

struct Edge

{

    int nxt,to;

}edge[200005];

int head[100005];

int ch[100005][2];

int f[100005];

int fa[100005][25];

int dep[100005];

int fl[100005];

int inr[100005],our[100005],onum[100005];

int cnt=1,tot;

int n,m;

void add(int l,int r)

{

    edge[cnt].nxt=head[l];

    edge[cnt].to=r;

    head[l]=cnt++;

}

void dfs(int x,int fx)

{

    dep[x]=dep[fx]+1,fa[x][0]=f[x]=fx,inr[x]=++tot,onum[tot]=x;

    for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];

    for(int i=head[x];i;i=edge[i].nxt)

    {

        int to=edge[i].to;

        if(to==fx)continue;

        dfs(to,x);

    }

    our[x]=tot;

}

int LCA(int x,int y)

{

    if(dep[x]>dep[y])swap(x,y);

    for(int i=20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y=fa[y][i];

    if(x==y)return x;

    int ret;

    for(int i=20;i>=0;i--)

    {

        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];

        else ret=fa[x][i];

    }

    return ret;

}

void buildtree(int rt,int l,int r)

{

    if(l==r){tree[rt].maxv=dep[onum[l]];return;}

    int mid=(l+r)>>1;

    buildtree(rt1,l,mid),buildtree(rt2,mid+1,r);

    tree[rt].maxv=max(tree[rt1].maxv,tree[rt2].maxv);

}

void down(int rt)

{

    tree[rt1].lazy+=tree[rt].lazy,tree[rt1].maxv+=tree[rt].lazy;

    tree[rt2].lazy+=tree[rt].lazy,tree[rt2].maxv+=tree[rt].lazy;

    tree[rt].lazy=0;

}

void update(int rt,int l,int r,int lq,int rq,int v)

{

    if(l>=lq&&r<=rq){tree[rt].lazy+=v;tree[rt].maxv+=v;return;}

    int mid=(l+r)>>1;

    if(tree[rt].lazy)down(rt);

    if(lq<=mid)update(rt1,l,mid,lq,rq,v);

    if(rq>mid)update(rt2,mid+1,r,lq,rq,v);

    tree[rt].maxv=max(tree[rt1].maxv,tree[rt2].maxv);

}

int query(int rt,int l,int r,int lq,int rq)

{

    if(l>=lq&&r<=rq)return tree[rt].maxv;

    int mid=(l+r)>>1;

    if(tree[rt].lazy)down(rt);

    int ret=0;

    if(lq<=mid)ret=max(ret,query(rt1,l,mid,lq,rq));

    if(rq>mid)ret=max(ret,query(rt2,mid+1,r,lq,rq));

    return ret;

}

bool be_root(int x)

{

    if(ch[f[x]][0]==x||ch[f[x]][1]==x)return 0;

    return 1;

}

void pushdown(int x)

{

    if(fl[x])

    {

        swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);

        swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);

        fl[ch[x][0]]^=1,fl[ch[x][1]]^=1;

        fl[x]=0;

    }

}

void repush(int x)

{

    if(!be_root(x))repush(f[x]);

    pushdown(x);

}

void rotate(int x)

{

    int y=f[x],z=f[y],k=(ch[y][1]==x);

    if(!be_root(y))ch[z][ch[z][1]==y]=x;

    f[x]=z;

    ch[y][k]=ch[x][!k],f[ch[x][!k]]=y;

    ch[x][!k]=y,f[y]=x;

}

void splay(int x)

{

    repush(x);

    while(!be_root(x))

    {

        int y=f[x],z=f[y];

        if(!be_root(y))

        {

            if((ch[y][1]==x)^(ch[z][1]==y))rotate(x);

            else rotate(y);

        }

        rotate(x);

    }

}

int get_root(int x)

{

    while(ch[x][0])x=ch[x][0];

    return x;

}

void access(int x)

{

    int y=0;

    while(x)

    {

        splay(x);

        if(ch[x][1])

        {

            int rt=get_root(ch[x][1]);

            update(1,1,n,inr[rt],our[rt],1);

        }

        ch[x][1]=y;

        if(y)

        {

            int rt=get_root(y);

            update(1,1,n,inr[rt],our[rt],-1);

        }

        y=x,x=f[x];

    }

}

inline int read()

{

    int f=1,x=0;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<n;i++)

    {

        int x=read(),y=read();

        add(x,y),add(y,x);

    }

    dfs(1,0),buildtree(1,1,n);

    while(m--)

    {

        int typ=read();

        if(typ==1)

        {

            int x=read();

            access(x);

        }else if(typ==2)

        {

            int x=read(),y=read(),fa=LCA(x,y);

            int s1=query(1,1,n,inr[x],inr[x]),s2=query(1,1,n,inr[y],inr[y]),s3=query(1,1,n,inr[fa],inr[fa]);

            printf("%d\n",s1+s2-2*s3+1);

        }else

        {

            int x=read();

            printf("%d\n",query(1,1,n,inr[x],our[x]));

        }

    }

    return 0;

}

巴特西

bzoj 4817

最新文章

热门文章