虚树
主要是针对这一类问题:答案只跟选定的某些点(及它们的 lca)有关,且选定点的总量可以接受
而每次询问都搜索一遍整棵树很浪费
因此建出虚树,在虚树上进行各种操作
构建
有两种方法:二次排序求 lca,单调栈
单调栈
单调栈上维护的是虚树的一条链
第一步肯定是将点按照 dfn 序排序
为了方便,先把根加入栈
加入点 \(x\) 时,先求出它和栈顶的最近公共祖先 \(lca\)
- 如果 \(lca\) 就是栈顶,那么 \(x\) 依然在这条链上,直接将 \(x\) 入栈,跳过
- 否则说明 \(x\) 在另外一条链上,先把栈中边的更高点 dfn 序都比 \(lca\) 大的边的下端点弹出并连这条边,被弹出的点不可能在新的链上
- 然后判定栈顶是否为 \(lca\)
- 如果栈顶是 \(lca\),那么说明 \(lca\) 已经入栈,跳过
- 否则 \(lca\) 一定是栈顶元素的祖先,连上 \(lca\) 与栈顶的边,弹出栈顶并加入 \(lca\)
- 最后将 \(x\) 入栈
不要忘记完成后栈内元素之间没有连边
但是我们在这个过程中默认了根在虚树中,很多情况下是没有问题的,如果题目要求比较特殊,根不能额外添加到虚树中,则插入时特判,如果根在点集中或者根在栈内元素连边之前已经有边,那么根本来就在虚树中,否则栈内元素连边时要跳过根
注意边的清空
void add(int u, int v) {edge[u].pb(v);}
void build(vector<int> p)
{
top = 0, stk[++top] = 1;
sort(p.begin(), p.end(), [](const int x, const int y){return dfn[x] < dfn[y];});
int flag = 0;
for(int x : p)
{
if(x == 1) {flag = 1; continue;}
int lca = getlca(stk[top], x); del.pb(lca);
while(top > 1 && dfn[stk[top - 1]] > dfn[lca]) add(stk[top - 1], stk[top]), --top;
if(dfn[lca] < dfn[stk[top]]) add(lca, stk[top]), --top; // 这里的 < 相当于 !=
if(!top || lca != stk[top]) stk[++top] = lca;
stk[++top] = x;
}
root = (!flag && !edge[1].size()) ? stk[2] : stk[1]; // 特判 1
for(int i = (!flag && !edge[1].size()) ? 3 : 2; i <= top; ++i) add(stk[i - 1], stk[i]);
}
二次排序
二次排序方法思路更简单,按 dfn 序排序后再对相邻元素求 lca,把得到的所有点再排序去重
然后就没了
比较
虽然不得不说二次排序思路简单,不容易写错
但个人还是比较喜欢用单调栈,因为我觉得单调栈这种动态加入构建的方式更有扩展性,常数较小,而且合并时由于 dfn 序已经有序,可以做到线性合并两个点集虚树
但每次动态加入一个点则需要二次排序的思路,插入 dfn 序对应位置后求与相邻两个数的 lca 并加入
性质
首先,虚树的大小为 \(O(|S|)\),这是构建方法和复杂度有保障的前提
如果将虚树上每个点到虚树的根的路径上所有点都加入虚树,那么,子节点数量 \(\ge 2\) 的点个数也只有 \(O(|S|)\)
虚树边权和为所有时间戳循环相邻的点距离之和除以 \(2\)
每条边会被正反经过各 \(1\) 次
虚树差分:如果把虚树上所有点到根路径上的点权值 \(+x\),则把关键点本身 \(+x\),dfn 序排序后相邻点的 \(lca\) 处 \(-x\),做树上前缀和(求子树内权值和)即可
同二次排序的过程
正权虚树的封闭性:
类比正权直径的封闭性,两个点集的直径可以合并得到新点集的直径
这里同理,定义点集前 \(k\) 大虚树为点集中选取 \(k\) 个点,使形成虚树的边权总和最大(当 \(k=2\) 时退化为直径)
那么两个点集的前 \(k\) 大虚树可以合并,先对点集中所有点建虚树,然后再上面用长链剖分的技巧,以直径端点为根,贪心选前 \(k-1\) 大长链,选出的叶子节点就是合并后虚树的关键点