虚树学习笔记

虚树

将树上某些关键点拿出来，保持一定祖先关系形成的树

性质

1. k个关键点构成的虚树大小上线为2k-1，在 虚树形态为一颗完全二叉树时实现
2. 虚树上节点集合为按dfs序排序后相邻节点的lca所构成的集合与关键点集合的并集

构建

不妨设dfs序先左后右
考虑按dfs序排序后增量构建与虚树的最右链
最右链：当前加入的最后一个点到虚树根的一条链（当前虚树最右端的链）
具体实现用栈来
当加入一个新点时，与最右链上的点进行比对，加入虚树
讨论加入新点x的情况，设y=lca(x,st[top])

1. 点x在st[top]的子树里
   在最右链中加入x即可
2. 点x不在st[top]的子树里且在st[top-1]的子树里且y不为st[top-1]
   此时y在st[top]到st[top-1]的路径上
   更新最右链（st[top-1]->st[top]变为st[top-1]->y->x），并将(st[top-1],st[top])加入虚树边集
3. 点x不在st[top]的子树里且在st[top-1]的子树里且y为st[top-1]
   更新最右链（st[top-1]->st[top]变为st[top-1]->x），并将(st[top-1],st[top])加入虚树边集
4. 点x不在st[top-1]的路径里
   根据y所在位置退栈更新最右链直至变为Case1/2/3

代码实现

int tp=0,len=0;
int st[maxn],b[maxn];
void ins(int x){
	if(tp==0){st[++tp]=x;b[++len]=x;return ;}
	int p=lca(st[tp],x);
	while(dep[st[tp-1]]>dep[p]){
		add(st[tp-1],st[tp]);
		tp--;
	}
	if(st[tp]!=p){
		if(st[tp-1]==p){add(st[tp-1],st[tp],0);tp--;}
		else{add(p,st[tp]);b[++len]=p;st[tp]=p;}
	}
	st[++tp]=x;b[++len]=x;
	return ;
}