蒟蒻不懂虚树的建立,求助
  • 板块学术版
  • 楼主starusc
  • 当前回复10
  • 已保存回复10
  • 发布时间2020/5/13 09:13
  • 上次更新2023/11/7 02:33:46
查看原帖
蒟蒻不懂虚树的建立,求助
49174
starusc楼主2020/5/13 09:13

为什么LCA为当前栈顶时,新加的点不用入栈啊?QWQ

(注释部分是错的)

inline void insert(int x){
	if(tp==1){st[++tp]=x;return;}
	int lca=LCA(st[tp],x);
	if(st[tp]==lca)return;//?
//	if(st[tp]==lca){st[++tp]=x;return;}
	while(tp>1&&dfn[st[tp-1]]>=dfn[lca]){ee[st[tp-1]].push_back(st[tp]);tp--;}
	if(st[tp]!=lca){ee[lca].push_back(st[tp]);st[tp]=lca;}
	st[++tp]=x;
}
2020/5/13 09:13
加载中...