§ 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;

Oct. 14, 2023 更新. 其实上面这个版本多跑了一次, 实际上只需要跑一次, 参见 OI-wiki.

int dfn[maxn];
bool valid[maxn];
int h[maxn], m, a[maxn], len;  // 存储关键点

bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // 按照 dfn 序排序
}

void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // 把关键点按照 dfn 序排序
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // 插入 lca
  }
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // 把所有虚树上的点按照 dfn 序排序
  len = unique(a + 1, a + len + 1) - a - 1;  // 去重
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // 连边，如有边权 就是 distance(lc,a[i+1])
  }
}