虚树
给定一棵树，树上有一些关键点，你要建另一棵树，保留关键点，以及任意一对关键点的 \(\text{LCA}\)。
当你发现对于一棵树，你只有一些关键点有用的时候，就可以尝试建虚树。
两次排序
思路
先把所有点按 \(\text{dfn}\) 序排序，然后把 \(\text{dfn}\) 相邻的两个点取出来，再把它们的 \(\text{LCA}\) 放进去。
再把所有点按 \(\text{dfn}\) 序排序，然后把 \(\text{dfn}\) 相邻的两个点取出来，设为 \(a_{i-1}\) 和 \(a_i\)，那么再把它们的 \(\text{LCA}\) 放进去，同时 \(a_i\) 的父亲就是它们的 \(\text{LCA}\)，连边即可。
核心代码
点击开 D
struct note {
int p; note(int p_=0) { p=p_; return ; }
friend bool operator < (const note a,const note b) {
return dfn[a.p]==dfn[b.p]?a.p<b.p:dfn[a.p]<dfn[b.p];
}
}; set<note> S={},nS={};
y=0,nS=S;
for(auto x:S) { if(y) {
z=lca(x.p,y),nS.insert(note(z));
} y=x.p; } S=nS;
y=0; for(auto x:S) { if(y) {
z=lca(x.p,y);
if(z!=x.p) G[z].insert(mkp(x.p,deep[x.p]-deep[z]));
nS.insert(note(z));
} y=x.p; } S=nS;
时间复杂度
假设有 \(k\) 个关键点，虚树一共 \(O(2k)\) 个点，时间复杂度是 \(O(k\log k)\)。
标签：note,text,笔记,初步,dfn,nS,虚树,关键点 From： https://www.cnblogs.com/fydj/p/18264041/vtree