已AC,关于LCT的疑惑
查看原帖
已AC,关于LCT的疑惑
431150
The_Last_Candy楼主2023/8/14 14:58

这是AC程序:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct LCT{
	int fa,son[2],tag;
}t[N];
inline int which(int x){return x == t[t[x].fa].son[1];}
inline bool isroot(int x){return x != t[t[x].fa].son[0] && x != t[t[x].fa].son[1];}
inline void rever(int x){if(!x) return; swap(t[x].son[0],t[x].son[1]); t[x].tag ^= 1;}
inline void pushdown(int x){if(!t[x].tag) return; rever(t[x].son[0]);rever(t[x].son[1]);t[x].tag = 0;}
inline void rorate(int x)
{
	int dir = which(x),y = t[x].fa,z = t[y].fa;
	t[y].son[dir] = t[x].son[dir ^ 1];
	if(t[x].son[dir ^ 1]) t[t[x].son[dir ^ 1]].fa = y;
	if(!isroot(y)) t[z].son[which(y)] = x;
	t[x].fa = z;
	t[x].son[dir ^ 1] = y;
	t[y].fa = x;
}
inline void splay(int x)
{
	int st[N],top = 0,now = x;
	while(!isroot(now)) st[++top] = now,now = t[now].fa; st[++top] = now;
	while(top) pushdown(st[top]),top--;
	while(!isroot(x))
	{
		if(!isroot(t[x].fa))
			rorate((which(x) ^ which(t[x].fa)) ? x : t[x].fa);
		rorate(x);
	}
}
inline void access(int x)
{
	for(int rc = 0;x;rc = x,x = t[x].fa)
		splay(x),t[x].son[1] = rc;
}
inline int findroot(int x)
{
	access(x);splay(x);
	while(t[x].son[0]) pushdown(x),x = t[x].son[0];
	splay(x);// 注意这里
	return x;
}
inline void makeroot(int x)
{
	access(x);splay(x);rever(x);
}
inline void link(int x,int y)
{
	makeroot(x);
	if(findroot(y) == x) return;
	t[x].fa = y;
}
inline void cut(int x,int y)
{
	makeroot(x);
	if(findroot(y) != x || t[y].fa != x || t[y].son[0]) return;
	t[y].fa = 0;t[x].son[1] = 0;
}
int main()
{
	int n,m;
	cin>>n>>m;
	string op;int x,y;
	for(int i = 1;i <= m;i++)
	{
		cin>>op>>x>>y;
		if(op == "Connect") link(x,y);
		if(op == "Destroy") cut(x,y);
		if(op == "Query") cout<<(findroot(x) == findroot(y) ? "Yes" : "No")<<endl;
	}
	return 0;
}

中间LCT找原来树上的根的地方是这样写的:

inline int findroot(int x)
{
	access(x);splay(x);
	while(t[x].son[0]) pushdown(x),x = t[x].son[0];
	splay(x);// 注意这里
	return x;
}

那个注释掉的地方理论上来说是用来调节时间复杂度的,但是删掉后第一个样例无法通过。这是为什么?

2023/8/14 14:58
加载中...