虚树浅学（偷学日记）
柒葉灬
2019-01-30 15:46:39
# 虚树偷（乱）学
---------
#### 概念：虚树就是重新造一棵不存在的树，
#### 相当于把原来树中有用的信息进行压缩，
#### 适用于那种多个询问，每次标记个别点的题目（或许）。
例题：[SDOI2011 消耗战 P2495](https://www.luogu.org/problemnew/show/P2495)
------
### 直接说如何造出虚树：
1. 把所有点按照dfn排序
2. 塞入一个点（按照需要塞，例如塞 $1$）
3. 找到之前按dfn排序后的的队列的第一个元素 $x$
4. 求出$x$与栈顶$stk[top]$的 $lca$
5. 如果$lca$不是$stk[top]$，$\dots \dots$，详细见代码。
6. 将$x$塞入栈，
7. 若队列非空，回到步骤$3$。
8. 把栈弹空。
代码中有详细注释。
### 模板：
```cpp
void add(int a,int b){//链压缩成边，（看情况取最大/小值）
if(dep[a]<dep[b])swap(a,b);
int tmp=a,dis=2e9;
for(int i=17;i>=0;i--){
if(dep[fa[a][i]]>=dep[b])
dis=min(dis,mn[a][i]),a=fa[a][i];
}
add_edge(b,tmp,dis);
}
bool cmp(int a,int b){
return dfn[a]<dfn[b];
}
void build(){
scanf("%d",&K);
for(int i=1;i<=K;i++)
scanf("%d",&num[i]);
sort(num+1,num+1+K,cmp);
stk[top=1]=1;
for(int i=1;i<=K;i++){
int lca=LCA(num[i],stk[top]);
if(lca!=stk[top]){
//核心部分
while(true){
if(dep[stk[top-1]]<=dep[lca]){
add(lca,stk[top]);
top--;
if(stk[top]!=lca)stk[++top]=lca;
break;
}
add(stk[top-1],stk[top]);
top--;
}
}
stk[++top]=num[i];
}
while(--top)add(stk[top],stk[top+1]);
}
```
虚树构造的复杂度，因为虚树构造的时候，
每添加一个点最多增加$2$个点。
所以树的大小最多是$2*k$个