我觉得这种东西就是工程题，好像这就是Splay的唯一用途吧
神仙的博客
#include<bits/stdc++.h>
#define lc(p) c[p][0]
#define rc(p) c[p][1]
using namespace std;
const int N=310000;
int f[N],c[N][2],v[N],s[N],st[N];
int t[N],n,m;
int nroot(int p){return lc(f[p])==p||rc(f[p])==p;}
void up(int x)
{
s[x]=s[lc(x)]^s[rc(x)]^v[x];
return;
}
void down(int x)
{
if(t[x])
{
swap(lc(x),rc(x));
t[x]=0; t[lc(x)]^=1,t[rc(x)]^=1;
}
return;
}
void rotate(int x)
{
int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y)) c[z][c[z][1]==y]=x;
c[x][!k]=y,c[y][k]=w;
if(w) f[w]=y;
f[y]=x,f[x]=z;
up(y);
}
void splay(int x)
{
int y=x,z=0;
st[++z]=y;
while(nroot(y)) st[++z]=y=f[y];
while(z>0) down(st[z--]);
while(nroot(x))
{
y=f[x],z=f[y];
if(nroot(y)) rotate((c[y][1]==x)^(c[z][1]==y)?x:y);
rotate(x);
}
up(x);
return;
}
void access(int x)
{
for(int y=0;x;x=f[y=x]) splay(x),rc(x)=y,up(x);
return;
}
void makeroot(int x)
{
access(x),splay(x);
t[x]^=1;
return;
}
int findroot(int x)
{
access(x),splay(x);
while(lc(x)) down(x),x=lc(x);
splay(x);
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y),splay(y);
return;
}
void link(int x,int y)
{
makeroot(x);
if(findroot(y)!=x) f[x]=y;
return;
}
void cut(int x,int y)
{
makeroot(x);
if(findroot(y)==x&&f[y]==x&&lc(y)==0)
{
f[y]=rc(x)=0;
up(x);
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
int op,x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&x,&y);
if(op==0) split(x,y),printf("%d
",s[y]);
else if(op==1) link(x,y);
else if(op==2) cut(x,y);
else splay(x),v[x]=y;
}
return 0;
}
题目
Tree II
#include<bits/stdc++.h>
#define lc(p) c[p][0]
#define rc(p) c[p][1]
using namespace std;
const int N=110000;
const int mod=51061;
int a[N],b[N],t[N];
int c[N][2],f[N],s[N],v[N],siz[N],st[N];
int n,q;
int nroot(int x){return lc(f[x])==x||rc(f[x])==x;}
void up(int x)
{
s[x]=((s[lc(x)]+s[rc(x)])%mod+v[x])%mod;
siz[x]=siz[lc(x)]+siz[rc(x)]+1;
return;
}
void D2(int x,int B)
{
v[x]=(v[x]+B)%mod;
s[x]=(s[x]+1ll*siz[x]*B%mod)%mod;
b[x]=(b[x]+B)%mod;
return;
}
void D1(int x,int A)
{
v[x]=1ll*v[x]*A%mod;
s[x]=1ll*s[x]*A%mod;
a[x]=1ll*a[x]*A%mod;
b[x]=1ll*b[x]*A%mod;
return;
}
void D3(int x)
{
t[x]^=1;
return;
}
void down(int x)
{
if(a[x]!=1)
{
if(lc(x)) D1(lc(x),a[x]);
if(rc(x)) D1(rc(x),a[x]);
a[x]=1;
}
if(b[x])
{
if(lc(x)) D2(lc(x),b[x]);
if(rc(x)) D2(rc(x),b[x]);
b[x]=0;
}
if(t[x])
{
swap(lc(x),rc(x));
if(lc(x)) D3(lc(x));
if(rc(x)) D3(rc(x));
t[x]=0;
}
return;
}
void rotate(int x)
{
int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nroot(y)) c[z][c[z][1]==y]=x;
c[x][!k]=y,c[y][k]=w;
if(w) f[w]=y;
f[y]=x,f[x]=z;
up(y);
return;
}
void splay(int x)
{
int y=x,z=0;
st[++z]=y;
while(nroot(y)) st[++z]=y=f[y];
while(z>0) down(st[z--]);
while(nroot(x))
{
y=f[x],z=f[y];
if(nroot(y)) rotate((c[y][1]==x)^(c[z][1]==y)?x:y);
rotate(x);
}
up(x);
return;
}
void access(int x)
{
for(int y=0;x;x=f[y=x]) splay(x),rc(x)=y,up(x);
return;
}
void makeroot(int x)
{
access(x);
splay(x);
t[x]^=1;
return;
}
int findroot(int x)
{
access(x),splay(x);
while(lc(x)) down(x),x=lc(x);
splay(x);
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
return;
}
void link(int x,int y)
{
makeroot(x),f[x]=y;
return;
}
void cut(int x,int y)
{
split(x,y);
lc(y)=f[x]=0;
up(y);
return;
}
void out()
{
for(int j=1;j<=n;j++) cout<<s[j]<<" "<<v[j]<<" "<<lc(j)<<" "<<rc(j)<<" "<<f[j]<<" "<<siz[j]<<" "<<a[j]<<" "<<b[j]<<endl;
return;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) v[i]=1,siz[i]=1,s[i]=1,a[i]=1,t[i]=lc(i)=rc(i)=0;
int u,v;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&u,&v);
link(u,v);
}
int ou,ov,c;
char op[5];
for(int i=1;i<=q;i++)
{
scanf("%s",op);
if(op[0]=='+')
{
scanf("%d%d%d",&u,&v,&c);
split(u,v);
D2(v,c);
}
else if(op[0]=='-')
{
scanf("%d%d%d%d",&u,&v,&ou,&ov);
cut(u,v);
link(ou,ov);
}
else if(op[0]=='*')
{
scanf("%d%d%d",&u,&v,&c);
split(u,v);
D1(v,c);
}
else
{
scanf("%d%d",&u,&v);
split(u,v);
printf("%d
",s[v]);
}
}
return 0;
}
- 数据结构还是要自己理解啊
维护虚子树
#include<bits/stdc++.h>
#define broken cerr << __FUNCTION__ <<" " << __LINE__ << endl
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
using namespace std;
typedef unsigned long long ul;
const int N = 1e5 + 10, M = 3e5 + 10;
int id, n, m;
int l[M], r[M], tot = 0;
int ch[N][2], fa[N], rev[N], st[N], top = 0;
ul v[N], s[N], key[M], sv[N], all = 0;
ul brd() {
ul x = rand();
x = (x << 16) | rand();
x = (x << 16) | rand(); x = (x << 16) | rand();
x ^= x << 31;
x ^= x >> 18;
x ^= x << 7;
return x ^ 20051047;
}
int nrt(int x) {
return lc(fa[x]) == x || rc(fa[x]) == x;
}
void upd(int x) {
s[x] = s[lc(x)] ^ s[rc(x)] ^ v[x] ^ sv[x];
return;
}
void pushd(int x) {
if(!rev[x]) return;
swap(lc(x), rc(x));
rev[x] = 0, rev[lc(x)] ^= 1, rev[rc(x)] ^= 1;
return;
}
void rotate(int x) {
int y = fa[x], z = fa[y];
int p = (ch[y][1] == x), k = ch[x][!p];
if(nrt(y)) ch[z][ch[z][1] == y] = x;
ch[x][!p] = y, ch[y][p] = k, fa[y] = x, fa[x] = z;
if(k) fa[k] = y;
return upd(y), void();
}
void splay(int x) {
int y = x;
top = 0;
st[++top] = x;
while(nrt(y)) st[++top] = y = fa[y];
while(top > 0) pushd(st[top--]);
while(nrt(x)) {
int y = fa[x], z = fa[y];
if(nrt(y)) rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y);
rotate(x);
}
return upd(x), void();
}
void access(int x) {
for(int y = 0; x; x = fa[y = x]) {
splay(x);
sv[x] ^= s[y] ^ s[rc(x)];
rc(x) = y;
upd(x);
}
return;
}
void makeroot(int x) {
access(x), splay(x), rev[x] ^= 1;
return;
}
void split(int x, int y) {
makeroot(x), access(y), splay(y);
return;
}
void link(int x, int y) {
split(x, y), fa[x] = y, sv[y] ^= s[x];
upd(y);
}
void cut(int x, int y) {
split(x, y), fa[x] = 0, ch[y][0] = 0;
upd(y);
}
void initnode(int n) {
for(int i = 1; i <= n; i++) rev[i] = lc(i) = rc(i) = s[i] = sv[i] = v[i] = 0;
return;
}
void modify(int x, ul y) {
access(x), splay(x), v[x] ^= y, upd(x);
return;
}
void put() {
for(int i = 1; i <= n; i++) {
cout << i <<" " << fa[i] <<" " << lc(i) <<" " << rc(i) << endl;
}
}
ul quer(int x, int y) {
cut(x, y);
makeroot(y);
ul sum = s[y];
link(x, y);
return sum == all;
}
int main() {
srand(time(NULL));
scanf("%d", &id);
scanf("%d%d", &n, &m);
initnode(n);
for(int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
link(u, v);
}
for(int amo = 1; amo <= m; amo++) {
int opt, x, y, u, v;
scanf("%d", &opt);
if(opt == 1) {
scanf("%d%d%d%d", &x, &y, &u, &v);
cut(x, y), link(u, v);
} else if(opt == 2) {
scanf("%d%d", &x, &y);
ul V = brd();
modify(x, V), modify(y, V);
l[++tot] = x, r[tot] = y, key[tot] = V, all ^= V;
} else if(opt == 3) {
scanf("%d", &x);
modify(l[x], key[x]), modify(r[x], key[x]), all ^= key[x];
} else {
scanf("%d%d", &x, &y);
printf(quer(x, y) ? "YES
" : "NO
");
}
}
return 0;
}