点击查看目录
目录
虚树，不是虚数 \(i\)。
定义
在树形 dp 等题目中，树中点很少，可以直接跑 dp。
但是如果很大但是我们只需要查询很少的一些点呢？
我们称某次询问的点为 【关键点】。
我们看上图，只有左边子树的两个节点被查询了，那右边的子树有 dp 的必要吗？
因此我们把一棵大树缩成一棵较小的树。
这就是【虚树】的概念
构造虚树
先来看看虚树的形态。
我们选择了查询结点，但是结点之间的 LCA 也是储存着信息的，需要加入。
以上道题来说，其虚树形态较为简单：
上一个比较大的虚树：
但是我们不可能 \(O(n^2)\) 两两查询 LCA，于是就很容易想到求一下 dfs 序，对于关键点放入一个容器排序，之后对于容器内相邻的关键点查询 LCA，加入虚树。
而如何构造虚树就成了难题。
无论虚树是什么样子，只要祖先与子孙的关系没有变，点就可以加入虚树。
所以为了方便，将 \(1\) 号节点首先加入虚树。
二次排序+LCA 连边
多个节点的 LCA 可能是同一个，不能多次加入。
因此我们将得到的需要加入的 LCA 和关键点第二次排序，然后去重即可。
然后，枚举这个数组的相邻两点 \(x\) 和 \(y\)，求得其 LCA 并连接 LCA 和 y。
证明其正确性：
-
首先明确：因为排序使得 \(x\) 和 \(y\) 的 dfs 序是相邻的，所以 \(x\to y\) 路径上没有关键点。
-
若 \(x\) 是 \(y\) 的祖先，那么直接让 \(x\) 连到 \(y\) 上。
-
若 \(x\) 不是 \(y\) 的祖先，则将 LCA 作为 \(y\) 的祖先连边即可。
-
而第一个点是我们加入的树根 \(1\)，所以不存在第一个点未与一个节点连接的可能。
总结，具体实现为以下步骤：
-
将关键点按照 dfs 序排序。
-
将数组中相邻的关键点的 LCA 加入数组。
-
将数组二次排序。
-
对数组进行去重。
-
对数组相邻的点寻找 LCA，连边。
Miku's Code
#define il inline
#define rg register int
int dfn[maxn];
bool vis[maxn];
int h[maxn],m,a[maxn],len;
bool comp(int x,int y) <% return dfn[x]<dfn[y]; %>
il void build_virtual_tree(){
sort(h+1,h+m+1,cmp);
for(rg i=1;i<m;++i){
a[++len]=h[i];
a[++len]=LCA(h[i],h[i + 1]);
}
a[++len]=h[m];
sort(a+1,a+len+1,comp);
len=unique(a+1,a+len+1)-(a+1);
for(rg i=1;i<len;++i){
int lca=LCA(a[i],a[i+1]);
add_edge2(lca,a[i+1]);
}
}
单调栈
米浴和你说说这个道理。
米浴说的道理—————
标签：int,笔记,学习,数组,LCA,排序,虚树,关键点 From： https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/Virtul_Tree-written_by_sonnety.html