求助LCT,改变断边连边函数即可AC
查看原帖
求助LCT,改变断边连边函数即可AC
333574
Tyyyyyy楼主2022/4/15 21:18

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 了,蒟蒻很不解,求助。

2022/4/15 21:18
加载中...