若每个节点存一个字符或权值,现在要快速匹配两条链,则可以使用此方法。
具体的操作和普通的 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);