Note -「virtual tree」shorter 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;