526互联

LCT维护树链哈希

发布时间 2023-06-22 00:01:09作者: 灵长同志

若每个节点存一个字符或权值，现在要快速匹配两条链，则可以使用此方法。

具体的操作和普通的 LCT 没有什么区别，但是十分的方便。

并且支持区间赋值等修改操作，十分优秀。

int base,p=100000267;
void csh(){fi[0]=1;for(int i=1;i<N;i++)fi[i]=(fi[i-1]*base)%p;}
struct link_cut_tree{
    int ch[N][2],f[N],st[N],hash[N],cnt[N];
    char val[N];
    bool r[N];
    #define lc ch[x][0]
    #define rc ch[x][1]
    void pushup(int x){
        cnt[x]=cnt[lc]+cnt[rc]+1;
        hash[x]=((hash[lc]*fi[cnt[rc]+1])%p+(val[x]-'a')*fi[cnt[rc]]%p+hash[rc])%p;
    }
    void rev(int x){swap(lc,rc),r[x]^=1;}
    int nroot(int x){return ch[f[x]][1]==x||ch[f[x]][0]==x;}
    int son(int x){return ch[f[x]][1]==x;}
    void rotate(int x){
        int y=f[x],z=f[y],k=son(x),w=ch[x][!k];
        if(nroot(y))ch[z][son(y)]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if(w)f[w]=y;
        f[x]=z,f[y]=x;
        pushup(y);
    }
    void pushdown(int x){
        if(r[x]){
            if(lc)rev(lc);
            if(rc)rev(rc);
            r[x]=0;
        }
    }
    void splay(int x){
        int y=x,z=0;
        st[++z]=y;
        while(nroot(y))st[++z]=y=f[y];
        while(z)pushdown(st[z--]);
        while(nroot(x)){
            y=f[x];
            if(nroot(y))rotate(son(x)!=son(y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    void access(int x){for(int y=0;x;x=f[y=x])splay(x),rc=y,pushup(x);}
    void makeroot(int x){access(x),splay(x),rev(x);}
    void split(int x,int y){makeroot(x),access(y),splay(y);}
    void link(int x,int y){makeroot(x),f[x]=y;}
}lct;

例题 CF504E

但是会被卡常，LCT 的常数过大

下面附上我的代码，有谁能帮我优化私信我，如果能帮我卡过，我感激不尽 qwq

#pragma comment(linker,"/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define fastcall __attribute__((optimize("-O3")))
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define N 614514
using namespace std;
int n,m;
int head[N],to[N],nxt[N],tot;
int fi[N];
char val[N],s[N];
int read(){
    int sum=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return sum*f;
}
void add(int u,int v){
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}
int son[N],top[N],id[N],idx,dep[N],siz[N],f[N];
int cid[N];
void dfs1(int x,int fa){
    dep[x]=dep[fa]+1;f[x]=fa;
    siz[x]=1;
    int mx=-1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==fa)continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(mx<siz[y])mx=siz[y],son[x]=y;
    }
}
void dfs2(int x,int topx){
    top[x]=topx;id[x]=++idx;s[idx]=val[x];
    cid[idx]=x;
    if(!son[x])return;
    dfs2(son[x],topx);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
int base,p=100000267;
void csh(){fi[0]=1;for(int i=1;i<N;i++)fi[i]=(fi[i-1]*base)%p;}
int lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
struct link_cut_tree{
    int ch[N][2],f[N],st[N],hash[N],cnt[N];
    char val[N];
    bool r[N];
    #define lc ch[x][0]
    #define rc ch[x][1]
    void pushup(int x){
        cnt[x]=cnt[lc]+cnt[rc]+1;
        hash[x]=((hash[lc]*fi[cnt[rc]+1])%p+(val[x]-'a')*fi[cnt[rc]]%p+hash[rc])%p;
    }
    void rev(int x){swap(lc,rc),r[x]^=1;}
    int nroot(int x){return ch[f[x]][1]==x||ch[f[x]][0]==x;}
    int son(int x){return ch[f[x]][1]==x;}
    void rotate(int x){
        int y=f[x],z=f[y],k=son(x),w=ch[x][!k];
        if(nroot(y))ch[z][son(y)]=x;
        ch[x][!k]=y,ch[y][k]=w;
        if(w)f[w]=y;
        f[x]=z,f[y]=x;
        pushup(y);
    }
    void pushdown(int x){
        if(r[x]){
            if(lc)rev(lc);
            if(rc)rev(rc);
            r[x]=0;
        }
    }
    void splay(int x){
        int y=x,z=0;
        st[++z]=y;
        while(nroot(y))st[++z]=y=f[y];
        while(z)pushdown(st[z--]);
        while(nroot(x)){
            y=f[x];
            if(nroot(y))rotate(son(x)!=son(y)?x:y);
            rotate(x);
        }
        pushup(x);
    }
    void access(int x){for(int y=0;x;x=f[y=x])splay(x),rc=y,pushup(x);}
    void makeroot(int x){access(x),splay(x),rev(x);}
    void split(int x,int y){makeroot(x),access(y),splay(y);}
    void link(int x,int y){makeroot(x),f[x]=y;}
}lct;
int query(int x,int y){
    lct.split(x,y);
    return lct.hash[y];
}
int quk(int x,int k,int rt){
    while(k>=id[x]-id[top[x]]+1&&x!=rt){
        k-=id[x]-id[top[x]]+1;
        x=f[top[x]];
    }
    return cid[id[x]-k];
}
int queryk(int x,int y,int k){
    int c=lca(x,y),d=dep[x]+dep[y]-2*dep[c]+1;
    if(k==1)return x;
    k--;
    if(k<dep[x]-dep[c]+1)return quk(x,k,c);
    else return quk(y,d-k-1,c);
}
int lcp(int a,int b,int c,int d){
    int lc1=lca(a,b),r1=dep[a]+dep[b]-2*dep[lc1]+1;
    int lc2=lca(c,d),r2=dep[c]+dep[d]-2*dep[lc2]+1;
    int l=1,r=min(r1,r2);
    while(l<=r){
        int mid=(l+r)>>1;
        int ar=queryk(a,b,mid),br=queryk(c,d,mid);
        if(query(a,ar)==query(c,br))l=mid+1;
        else r=mid-1;
    }
    return r;
}
signed main(){
    srand(time(0));
    base=rand()%200*10+rand()%2000;
    scanf("%d",&n);
    scanf("%s",val+1);
    csh();
    for(int i=1;i<=n;i++)lct.val[i]=val[i],lct.cnt[i]=1;
    for(int i=1;i<n;i++){
        int a,b;
        a=read(),b=read();
        lct.link(a,b);
        add(a,b);add(b,a);
    }
    dfs1(1,0);dfs2(1,1);
    scanf("%d",&m);
    while(m--){
        int a=read(),b=read(),c=read(),d=read();
        printf("%d\n",lcp(a,b,c,d));
    }
    return 0;
}

完结撒花。