rt,这是我第一次提交的代码,全wa,这个LCT通过了模板题:
#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
namespace IO
{
const int SZ=1<<20;
char gchar()
{
static char buf[SZ];
static int i=SZ;
if(i==SZ)i=0,fread(buf,1,SZ,stdin);
return buf[i++];
}
void pchar(char c)
{
static char buf[SZ];
static int i=0;
if(c)buf[i++]=c;
if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
}
template<typename T>void read(T &x)
{
x=0;
static char c;
while((c=gchar())>'9'||c<'0');
x=c-'0';
while((c=gchar())>='0'&&c<='9')
x=(x<<1)+(x<<3)+(c^48);
}
template<typename T>void i_write(T x)
{
if(x>9)i_write(x/10);
pchar(x%10+'0');
}
template<typename T>void write(T x,char end='\n')
{
if(x<0)pchar('-'),x=-x;
if(x>9)i_write(x/10);
pchar(x%10+'0');
pchar(end);
}
}
using IO::read;
using IO::write;
const int N=1e5+10;
struct Link_Cut_Tree
{
int fa[N],ch[N][2],siz[N],siz2[N],stk[N],top;
bool rev[N];
bool nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
void pushup(int x)
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1+siz2[x];
}
void adrev(int x){swap(ch[x][0],ch[x][1]);rev[x]^=1;}
void pushdown(int x)
{
if(rev[x])adrev(ch[x][0]),adrev(ch[x][1]),rev[x]=0;
}
void rotate(int x)
{
int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][!k];
if(nroot(y))ch[z][ch[z][1]==y]=x;
ch[x][!k]=y,ch[y][k]=w;
if(w)fa[w]=y;
fa[y]=x,fa[x]=z;
pushup(y);
}
void splay(int x)
{
int y=x;top=0;
stk[++top]=y;
while(nroot(y))stk[++top]=(y=fa[y]);
while(top)pushdown(stk[top--]);
while(nroot(x))
{
y=fa[x];int z=fa[y];
if(nroot(y))rotate(((ch[y][0]==x)^(ch[z][0]==y))?x:y);
rotate(x);
}
pushup(x);
}
void access(int x)
{
for(int y=0;x;x=fa[y=x])
splay(x),siz2[x]+=siz[ch[x][1]]-siz[y],ch[x][1]=y,pushup(x);
}
void makeroot(int x)
{
access(x),splay(x),adrev(x);
}
int findroot(int x)
{
access(x),splay(x);
while(ch[x][0])pushdown(x),x=ch[x][0];
splay(x);return x;
}
void split(int x,int y)
{
makeroot(x),access(y),splay(y);
}
void link(int x,int y)
{
makeroot(x);
if(findroot(y)!=x)fa[x]=y,siz2[y]+=siz[x];
}
void cut(int x,int y)
{
makeroot(x);
if(findroot(y)==x&&fa[y]==x&&!ch[y][0])
fa[y]=ch[x][1]=0,pushup(x);
}
}tr;
int n,q;
int main()
{
read(n),read(q);
char c;int x,y;
while(q--)
{
c=IO::gchar();
while(c!='A'&&c!='Q')c=IO::gchar();
read(x),read(y);
if(c=='A')tr.link(x,y);
else
{
tr.split(x,y),tr.cut(x,y);
write(1ll*tr.siz[x]*tr.siz[y]);
tr.link(x,y);
}
}
IO::pchar(0);
return 0;
}
之后在查询时将删边改成了这样:
tr.ch[y][0]=tr.fa[x]=0,tr.pushup(x);
然后 link 函数中加上了 makeroot(y) 并删掉了 pushup(y) 就 AC 了,蒟蒻很不解,求助。