Note -「Virtual Tree」一种更短的 VRT 写法

Part. 1 Preface

没什么 preface。

Part. 2 实现

具体来说就是把所有关键点按 \(\text{dfn}\) 排序，去重，然后求出相邻结点的 \(\text{LCA}\)，然后加入关键点，去重；然后把关键点和加入的 \(\text{LCA}\) 一起按 \(\text{dfn}\) 排序，最后把两两之间的 \(\text{LCA}\) 拿出来当爸爸然后把右边当儿子。

草说不清楚自己看代码，比传统维护右链代码不知道短到哪里去了。

struct VirtualTree
{
	vector<int> e[1000010]; // 连出来的虚树
	vector<int> build(vector<int> poi) // poi：关键点
	{
		sort(poi.begin(),poi.end(),cmp);
		poi.erase(unique(poi.begin(),poi.end()),poi.end());
		int len=poi.size();
		for(int i=0;i<len-1;++i)	poi.push_back(LCA(poi[i],poi[i+1]));
		sort(poi.begin(),poi.end(),cmp);
		poi.erase(unique(poi.begin(),poi.end()),poi.end());
		len=poi.size();
		for(int i=1;i<len;++i)	e[LCA(poi[i-1],poi[i])].push_back(poi[i]);
		return poi;
	}
}VRT;

Note -「Virtual Tree」一种更短的 VRT 写法

原文：https://www.cnblogs.com/orchid-any/p/14471100.html