LCT裸题泛做

时间：2023-12-28 13:15:44

①洞穴勘测 bzoj2049

题意：由若干个操作，每次加入/删除两点间的一条边，询问某两点是否连通。保证任意时刻图都是一个森林。（两点之间至多只有一条路径）

这就是个link+cut+find root的裸题啦。

LCT实现的时候注意在splay的时候要提前把所有点pushdown一下，详见代码。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <math.h>

#include <limits>

#include <set>

#include <map>

using namespace std;

#define SZ 233333

int ch[SZ][2],fa[SZ];

bool rev[SZ];

bool top(int x) {return !(ch[fa[x]][0]==x||ch[fa[x]][1]==x);}

void pd(int x)

{

    if(!rev[x]) return;

    rev[x]=0;

    rev[ch[x][0]]^=1;

    rev[ch[x][1]]^=1;

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

}

void rot(int x)

{

    if(top(x)) return;

    int y=fa[x],c=ch[y][0]==x;

    int f=fa[y];

    if(!top(y)) ch[f][ch[f][1]==y]=x; //不能直接判f

    if(ch[x][c]) fa[ch[x][c]]=y;

    ch[y][!c]=ch[x][c];

    ch[x][c]=y; fa[x]=f; fa[y]=x;

    //upd(y); upd(x);

}

int ss[SZ],sn;

void splay(int x)

{

    sn=0;

    for(int c=x;;c=fa[c])

    {

        ss[++sn]=c;

        if(top(c)) break;

    }

    while(sn) pd(ss[sn--]);

    while(!top(x))

    {

        int y=fa[x];

        if(!top(y))

        {

            if(ch[fa[y]][0]==y^ch[y][0]==x) rot(x);

            else rot(y);

        }

        rot(x);

    }

}

void access(int x)

{

    for(int c=0;x;c=x,x=fa[x]) splay(x), ch[x][1]=c;

}

void makeroot(int x) {access(x); splay(x); rev[x]^=1;}

void link(int a,int b) {makeroot(a); fa[a]=b;}

void cut(int a,int b) {makeroot(a); access(b); splay(b); ch[b][0]=fa[a]=0;}

int findroot(int x)

{

    access(x); splay(x);

    int lc=x;

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

    splay(lc); return lc;

}

int main()

{

    int n,q;

    scanf("%d%d",&n,&q);

    while(q--)

    {

        char s[20]; int a,b;

        scanf("%s%d%d",s,&a,&b);

        if(s[0]=='Q')

        {

            if(findroot(a)==findroot(b)) puts("Yes");

            else puts("No");

        }

        else if(s[0]=='C') link(a,b);

        else cut(a,b);

    }

}

②树的统计 bzoj1036

题意：给一棵树，要兹磁点权修改，询问两点间路径最大点权/点权和。

其实讲道理的话这题是可以直接上链剖的，但是还是砍手写了个LCT。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <math.h>

#include <limits>

#include <set>

#include <map>

using namespace std;

#define SZ 233333

int ch[SZ][2],fa[SZ],sum[SZ],vv[SZ],mx[SZ];

bool rev[SZ];

bool top(int x) {return !(ch[fa[x]][0]==x||ch[fa[x]][1]==x);}

void pd(int x)

{

    if(!rev[x]) return;

    rev[x]=0;

    rev[ch[x][0]]^=1;

    rev[ch[x][1]]^=1;

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

}

void upd(int x)

{

    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+vv[x];

    mx[x]=max(max(mx[ch[x][0]],mx[ch[x][1]]),vv[x]);

}

void rot(int x)

{

    if(top(x)) return;

    int y=fa[x],c=ch[y][0]==x;

    int f=fa[y];

    if(!top(y)) ch[f][ch[f][1]==y]=x; //不能直接判f

    if(ch[x][c]) fa[ch[x][c]]=y;

    ch[y][!c]=ch[x][c];

    ch[x][c]=y; fa[x]=f; fa[y]=x;

    upd(y); upd(x);

}

int ss[SZ],sn;

void splay(int x)

{

    sn=0;

    for(int c=x;;c=fa[c])

    {

        ss[++sn]=c;

        if(top(c)) break;

    }

    while(sn) pd(ss[sn--]);

    while(!top(x))

    {

        int y=fa[x];

        if(!top(y))

        {

            if(ch[fa[y]][0]==y^ch[y][0]==x) rot(x);

            else rot(y);

        }

        rot(x);

    }

}

void access(int x)

{

    for(int c=0;x;c=x,x=fa[x]) splay(x), ch[x][1]=c, upd(x);

}

void makeroot(int x) {access(x); splay(x); rev[x]^=1;}

void link(int a,int b) {makeroot(a); fa[a]=b;}

void cut(int a,int b) {makeroot(a); access(b); splay(b); ch[b][0]=fa[a]=0;}

int findroot(int x)

{

    access(x); splay(x);

    int lc=x;

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

    splay(lc); return lc;

}

int ea[SZ],eb[SZ];

int main()

{

    int n,q; mx[0]=-2000000000; //wtf...

    scanf("%d",&n);

    for(int i=1;i<n;i++) scanf("%d%d",ea+i,eb+i);

    for(int i=1;i<=n;i++) scanf("%d",vv+i), sum[i]=mx[i]=vv[i];

    for(int i=1;i<n;i++) link(ea[i],eb[i]);

    scanf("%d",&q);

    while(q--)

    {

        char s[20]; int a,b;

        scanf("%s%d%d",s,&a,&b);

        if(s[0]=='C')

        {

            vv[a]=b; splay(a); //玄学

        }

        else

        {

            makeroot(a);

            access(b);

            splay(b);

            if(s[1]=='M') printf("%d\n",mx[b]);

            else printf("%d\n",sum[b]);

        }

    }

}

③弹飞绵羊 bzoj2002

题意：有两种操作，改变或删除一个点的父亲，询问一个点的深度。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <math.h>

#include <limits>

#include <set>

#include <map>

using namespace std;

#define SZ 233333

int ch[SZ][2],fa[SZ],siz[SZ];

bool rev[SZ];

bool top(int x) {return !(ch[fa[x]][0]==x||ch[fa[x]][1]==x);}

void pd(int x)

{

    if(!rev[x]) return;

    rev[x]=0;

    rev[ch[x][0]]^=1;

    rev[ch[x][1]]^=1;

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

}

void upd(int x)

{

    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;

}

void rot(int x)

{

    if(top(x)) return;

    int y=fa[x],c=ch[y][0]==x;

    int f=fa[y];

    if(!top(y)) ch[f][ch[f][1]==y]=x; //不能直接判f

    if(ch[x][c]) fa[ch[x][c]]=y;

    ch[y][!c]=ch[x][c];

    ch[x][c]=y; fa[x]=f; fa[y]=x;

    upd(y); upd(x);

}

int ss[SZ],sn;

void splay(int x)

{

    sn=0;

    for(int c=x;;c=fa[c])

    {

        ss[++sn]=c;

        if(top(c)) break;

    }

    while(sn) pd(ss[sn--]);

    while(!top(x))

    {

        int y=fa[x];

        if(!top(y))

        {

            if(ch[fa[y]][0]==y^ch[y][0]==x) rot(x);

            else rot(y);

        }

        rot(x);

    }

}

void access(int x)

{

    for(int c=0;x;c=x,x=fa[x]) splay(x), ch[x][1]=c, upd(x);

}

void makeroot(int x) {access(x); splay(x); rev[x]^=1;}

void link(int a,int b) {makeroot(a); fa[a]=b;}

void cut(int a,int b) {makeroot(a); access(b); splay(b); ch[b][0]=fa[a]=0;}

int findroot(int x)

{

    access(x); splay(x);

    int lc=x;

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

    splay(lc); return lc;

}

int tl[SZ];

int main()

{

    int n; scanf("%d",&n);

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

    {

        scanf("%d",tl+i);

        link(i+1,min(i+1+tl[i],n+1));

    }

    int q; scanf("%d",&q);

    while(q--)

    {

        int a;

        scanf("%d",&a);

        if(a==1)

        {

            int b; scanf("%d",&b); ++b;

            makeroot(n+1);

            access(b); splay(b);

            printf("%d\n",siz[b]-1);

        }

        else

        {

            int i; scanf("%d",&i);

            cut(i+1,min(i+1+tl[i],n+1));

            scanf("%d",tl+i);

            link(i+1,min(i+1+tl[i],n+1));

        }

    }

}

④魔法森林 NOI2014 uoj3 bzoj3669

题意：无向图中一条边有两个权值a和b，求一条从1到n的路径使经过边a的最大值+经过边b的最大值最小。

我们把边权按a排个序，然后我们现在就是要维护每次动态加一条边和求一条从1到n的路径使得经过边b的最大值最小。

如果询问用spfa硬刚的话复杂度玄学，但是在NOI中可以拿到100分（当然UOJ上只能拿到97分

当然我们可以用lct做，也很简单，我们加一条边(x,y,b=v)只要看一下当前x到y的路径上b的最大值，如果根本就不连通或者最大值大于v，我们就把最大的那条边删掉，把这条边加进去。

那么似乎还有一个问题，lct似乎不好维护边权…但仔细想想你只要把边也当成点就行。

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <math.h>

#include <limits>

#include <set>

#include <map>

using namespace std;

#define SZ 233333

int ch[SZ][2],fa[SZ],sum[SZ],vv[SZ],mx[SZ];

bool rev[SZ];

bool top(int x) {return !(ch[fa[x]][0]==x||ch[fa[x]][1]==x);}

void pd(int x)

{

    if(!rev[x]) return;

    rev[x]=0;

    rev[ch[x][0]]^=1;

    rev[ch[x][1]]^=1;

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

}

void upd(int x)

{

    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+vv[x];

    if(vv[mx[ch[x][0]]]>vv[mx[ch[x][1]]]&&vv[mx[ch[x][0]]]>vv[x]) mx[x]=mx[ch[x][0]];

    else if(vv[mx[ch[x][1]]]>vv[x]) mx[x]=mx[ch[x][1]];

    else mx[x]=x;

}

void rot(int x)

{

    if(top(x)) return;

    int y=fa[x],c=ch[y][0]==x;

    int f=fa[y];

    if(!top(y)) ch[f][ch[f][1]==y]=x; //不能直接判f

    if(ch[x][c]) fa[ch[x][c]]=y;

    ch[y][!c]=ch[x][c];

    ch[x][c]=y; fa[x]=f; fa[y]=x;

    upd(y); upd(x);

}

int ss[SZ],sn;

void splay(int x)

{

    sn=0;

    for(int c=x;;c=fa[c])

    {

        ss[++sn]=c;

        if(top(c)) break;

    }

    while(sn) pd(ss[sn--]);

    while(!top(x))

    {

        int y=fa[x];

        if(!top(y))

        {

            if(ch[fa[y]][0]==y^ch[y][0]==x) rot(x);

            else rot(y);

        }

        rot(x);

    }

}

void access(int x)

{

    for(int c=0;x;c=x,x=fa[x]) splay(x), ch[x][1]=c, upd(x);

}

void makeroot(int x) {access(x); splay(x); rev[x]^=1;}

void link(int a,int b) {makeroot(a); fa[a]=b;}

void cut(int a,int b) {makeroot(a); access(b); splay(b); ch[b][0]=fa[a]=0;}

int findroot(int x)

{

    access(x); splay(x);

    int lc=x;

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

    splay(lc); return lc;

}

int getrd(int a,int b) {makeroot(a); access(b); splay(b); return b;}

int n,m;

struct edg {int x,y,a,b;}es[233333];

bool operator < (edg a,edg b) {return a.a<b.a;}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++) scanf("%d%d%d%d",&es[i].x,&es[i].y,&es[i].a,&es[i].b);

    sort(es+1,es+1+m);

    int ans=2000000000;

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

    {

        int x=es[i].x,y=es[i].y,a=es[i].a,b=es[i].b;

        vv[i+n]=b;

        if(findroot(x)==findroot(y))

        {

            int p=mx[getrd(x,y)];

            if(vv[p]<=b) continue;

            cut(p,es[p-n].x);

            cut(p,es[p-n].y);

        }

        link(x,i+n); link(i+n,y);

        if(findroot(1)==findroot(n)) ans=min(ans,vv[mx[getrd(1,n)]]+a);

    }

    if(ans==2000000000) ans=-1;

    printf("%d\n",ans);

}
//似乎有个地方写错了...欢迎hack

相关文章