虚树¶
虚树 Virtual Tree，指的是在树上，对于一道有稀疏的点需要查询信息（我们称之为查询点），并且对于非查询点的信息不重要的情况下使用。
虚树即把原树上的查询点，查询点的LCA和根节点保留下来的新树，其规模会比原树小很多。
它重要用来优化树形dp或者树上搜索的复杂度。
建树流程¶
const int N=100005,M=N*2;
int h[N],to[M],ne[M],tot;
void add(int x,int y){ //连边
to[++tot]=y;ne[tot]=h[x];h[x]=tot;
}
int dep[N],fa[N][20],siz[N];
int dfn[N],cnt; //dfs序
int s[N],top; //栈
int n,k,q,a[N],ans;
void dfs(int x, int f){ //树上倍增
dfn[x]=++cnt;
dep[x]=dep[f]+1; fa[x][0]=f; siz[x]=1;
for(int i=1; i<=19; i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=h[x]; i; i=ne[i]){
int y=to[i];
if(y==f) continue;
dfs(y,x);
siz[x]+=siz[y];
}
}
int lca(int x, int y){ //求lca
if(dep[x]<dep[y])swap(x, y);
for(int i=19; ~i; i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return y;
for(int i=19; ~i; i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i], y=fa[y][i];
return fa[x][0];
}
int cmp(int a,int b){
return dfn[a]<dfn[b];
}
void build(){ //建虚树
sort(a+1,a+k+1,cmp); //按dfs序排序
tot=0; //清空
s[top=1]=1; //根节点入栈
if(a[1]!=1) s[++top]=a[1];
for(int i=2; i<=k; i++){ //枚举查询点
int l=lca(s[top],a[i]);
// 对当前链连边,top出栈
while(top>1 && dep[s[top-1]]>=dep[l])
add(s[top-1],s[top]), top--;
// 对lca和top连边,top出栈,lca入栈
if(l!=s[top]) add(l,s[top]), s[top]=l;
// 查询点入栈
s[++top]=a[i];
}
while(top) //对最后一条链连边,top出栈
add(s[top-1],s[top]), top--;
}
例题 #1 Kingdom and its Cities¶
一个王国有n座城市，城市之间由n-1条道路相连，形成一个树结构，国王决定将一些城市设为重要城市。
这个国家有的时候会遭受外敌入侵，重要城市由于加强了防护，一定不会被占领。而非重要城市一旦被占领，这座城市就不能通行。
国王定了若干选择重要城市的计划，他想知道，对于每个计划，外敌至少要占领多少个非重要城市，才会导致重要城市之间两两不连通。如果外敌无论如何都不可能导致这种局面，输出-1
感谢@litble 提供的翻译
The first line of the input contains integer \(n\) ( \(1<=n<=100000\) ) — the number of cities in the kingdom.
Each of the next \(n-1\) lines contains two distinct integers \(u_{i}\) , \(v_{i}\) ( \(1<=u_{i},v_{i}<=n\) ) — the indices of the cities connected by the \(i\) -th road. It is guaranteed that you can get from any city to any other one moving only along the existing roads.
The next line contains a single integer \(q\) ( \(1<=q<=100000\) ) — the number of King's plans.
Each of the next \(q\) lines looks as follows: first goes number \(k_{i}\) — the number of important cities in the King's plan, ( \(1<=k_{i}<=n\) ), then follow exactly \(k_{i}\) space-separated pairwise distinct numbers from 1 to \(n\) — the numbers of important cities in this plan.
The sum of all \(k_{i}\) 's does't exceed \(100000\) .
我们可以先将树变成虚树，然后进行dfs：
首先我们赋值\(sz_u=[u是一个关键点?1:0]\)
若dfs到一个查询点u（以下我们称其为关键点，即重要城市），我们先dfs下去。在每次dfs其一个儿子\(v_i\)后，若\(sz_{v_i}>0\)，则说明其下方链接了一个关键点，并且由于dfs性质，这个关键点没有和u断开。那么此次我们就需要断开链接。
注意断开链接其实是删除u和其下方关键点路径上的任意一个非关键点。所以如果两个关键点之间没有如何非关键点，则必然无解。
当dfs到一个非关键点u，那么u必然是某两个关键点的lca。dfs下去，且在递归完其所有儿子后求和\(sum=\sum_{v_i\in son(u)} sz_{v_i}\)。若sum≥2，则说明有至少两个关键点通过u相连。此时就需要删除u。否则不需要。
// 树上倍增+虚树+树形DP 150ms
#include<bits/stdc++.h>
// luogu-judger-enable-o2
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
// #define int long long
#define pii pair<int,int>
#define lc(x) (x<<1)
#define rc(x) (x<<1|1)
#define rd read()
inline int read(){
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out){
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N=100005,M=N*2;
int h[N],to[M],ne[M],tot;
void add(int x,int y){ //连边
to[++tot]=y;ne[tot]=h[x];h[x]=tot;
}
int dep[N],fa[N][20],siz[N];
int dfn[N],cnt; //dfs序
int s[N],top; //栈
int n,k,q,a[N],ans;
void dfs(int x, int f){ //树上倍增
dfn[x]=++cnt;
dep[x]=dep[f]+1; fa[x][0]=f; siz[x]=1;
for(int i=1; i<=19; i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=h[x]; i; i=ne[i]){
int y=to[i];
if(y==f) continue;
dfs(y,x);
siz[x]+=siz[y];
}
}
int lca(int x, int y){ //求lca
if(dep[x]<dep[y])swap(x, y);
for(int i=19; ~i; i--)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return y;
for(int i=19; ~i; i--)
if(fa[x][i]!=fa[y][i])
x=fa[x][i], y=fa[y][i];
return fa[x][0];
}
int cmp(int a,int b){
return dfn[a]<dfn[b];
}
void build(){ //建虚树
sort(a+1,a+k+1,cmp); //按dfs序排序
tot=0; //清空
s[top=1]=1; //根节点入栈
if(a[1]!=1) s[++top]=a[1];
for(int i=2; i<=k; i++){ //枚举查询点
int l=lca(s[top],a[i]);
// 对当前链连边,top出栈
while(top>1 && dep[s[top-1]]>=dep[l])
add(s[top-1],s[top]), top--;
// 对lca和top连边,top出栈,lca入栈
if(l!=s[top]) add(l,s[top]), s[top]=l;
// 查询点入栈
s[++top]=a[i];
}
while(top) //对最后一条链连边,top出栈
add(s[top-1],s[top]), top--;
}
void DP(int x){ //树形DP
if(siz[x]){ //x是查询点
for(int i=h[x]; i; i=ne[i]){
DP(to[i]);
if(siz[to[i]]) ans++, siz[to[i]]=0;
}
}
else{ //x不是查询点
for(int i=h[x]; i; i=ne[i]){
DP(to[i]);
siz[x]+=siz[to[i]], siz[to[i]]=0;
}
if(siz[x]>1) ans++, siz[x]=0;
}
h[x]=0; //清空
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
memset(h+1,0,n<<2);
memset(siz+1,0,n<<2); //清空
scanf("%d",&q);
while(q--){
scanf("%d",&k);
bool flag=0; siz[1]=0; //清空
for(int i=1; i<=k; i++)
scanf("%d",&a[i]),siz[a[i]]=1;
for(int i=1; i<=k; i++)
if(siz[fa[a[i]][0]]){ //无解
while(k) siz[a[k--]]=0; //清空
puts("-1"); flag=1; break;
}
if(flag) continue;
build();
ans=0; DP(1);
printf("%d\n",ans);
}
return 0;
}
例题 #2 [SDOI2011] 消耗战¶
题目描述
在一场战争中，战场由 \(n\) 个岛屿和 \(n-1\) 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 \(1\) 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 \(k\) 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。
侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 \(1\) 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 \(m\) 次，所以我们只需要把每次任务完成即可。
输入格式
第一行一个整数 \(n\)，表示岛屿数量。
接下来 \(n-1\) 行，每行三个整数 \(u,v,w\) ，表示 \(u\) 号岛屿和 \(v\) 号岛屿由一条代价为 \(w\) 的桥梁直接相连。
第 \(n+1\) 行，一个整数 \(m\) ，代表敌方机器能使用的次数。
接下来 \(m\) 行，第 \(i\) 行一个整数 \(k_i\) ，代表第 \(i\) 次后，有 \(k_i\) 个岛屿资源丰富。接下来 \(k_i\) 个整数 \(h_1,h_2,..., h_{k_i}\) ，表示资源丰富岛屿的编号。
输出格式
输出共 \(m\) 行，表示每次任务的最小代价。
- 对于 \(100\%\) 的数据，\(2\leq n \leq 2.5\times 10^5, 1\leq m\leq 5\times 10^5, \sum k_i \leq 5\times 10^5, 1\leq k_i< n, h_i\neq 1, 1\leq u,v\leq n, 1\leq w\leq 10^5\) 。
解决虚数问题要考虑到两点
-
最基础的树形dp模型和方法
-
可以使用虚数来去除无用数据和降低复杂度
那么我们先考虑第一条。那么就是树形dp。我们知道倍增可以处理区间最小值，那么我们就可以使用倍增维护树上任意路径上的最小值。我们在树形dp时设\(f_i\)为使得i节点的父亲不能到达i节点中的任意一个关键点的最小费用即可。
那么在构建虚树时，我们用树上倍增快速处理出两个关键点u,v（或者关键点u与LCA v）之间的路径上的最小边权w，将虚树u-v的权值设置为w，跑树上dp即可。
这要求我们构建虚树的复杂度必须与n无关而与k有关。而建虚树恰好满足。
/*
CB Ntsc
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second
#define err cerr << "Error"
#define rd read()
// #define nl putc('\n')
#define ot write
#define nl putchar('\n')
int rd {
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
const int INF = 1e13;
const int N = 2e5 + 5;
const int M = 1e6 + 5;
const int S = 1e6 + 5;
const int maxlog = 10;
struct data {
int v, nxt, val;
} edge[2 * N];
int alist[N];
int cnt;
int n;
void add(int u, int v, int val) {
edge[++cnt].v = v;
edge[cnt].nxt = alist[u];
alist[u] = cnt;
edge[cnt].val = val;
}
int dfu,dfin[N],dfou[N],fa[22][N],mi[N],dep[N];
void dfs(int x)
{
dfin[x] = ++dfu;
for (int i = 1; fa[i - 1][x]; i++) {
fa[i][x] = fa[i - 1][fa[i - 1][x]];
}
int nxt = alist[x];
while (nxt) {
int v = edge[nxt].v;
int val = edge[nxt].val;
if (dfin[v] == 0) {
dep[v] = dep[x] + 1;
mi[v] = min(mi[x], val);
fa[0][v] = x;
dfs(v);
}
nxt = edge[nxt].nxt;
}
dfou[x] = ++dfu;
return;
}
int lca(int u, int v)
{
if (dep[u] < dep[v])
swap(u, v);
int del = dep[u] - dep[v];
for (int i = 0; del; del >>= 1, i++) {
if (del & 1) {
u = fa[i][u];
}
}
if (u == v) {
return u;
}
for (int i = 20; i >= 0; i--) {
if (fa[i][u] != fa[i][v]) {
u = fa[i][u];
v = fa[i][v];
}
}
return fa[0][v];
}
int tr[4 * N];
stack<int> s;
int m;
bool book[N];
int sum[N];
bool cmp(int x, int y)
{
int k1 = (x > 0) ? dfin[x] : dfou[-x];
int k2 = (y > 0) ? dfin[y] : dfou[-y];
return k1 < k2;
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i < n; i++) {
int u, v, val;
scanf("%lld%lld%lld", &u, &v, &val);
add(u, v, val);
add(v, u, val);
}
mi[1] = 0x7f7f7f7f;
dfs(1);
scanf("%lld", &m);
for (int i = 1; i <= m; i++) {
int cot;
scanf("%lld", &cot);
for (int j = 1; j <= cot; j++) {
scanf("%lld", &tr[j]);
book[tr[j]] = true;
sum[tr[j]] = mi[tr[j]];
}
sort(tr + 1, tr + cot + 1, cmp);
for (int j = 1; j < cot; j++)
{
int lc = lca(tr[j], tr[j + 1]);
if (!book[lc]) {
tr[++cot] = lc;
book[lc] = true;
}
}
int nc = cot;
for (int j = 1; j <= nc; j++) {
tr[++cot] = -tr[j];
}
if (!book[1]) {
tr[++cot] = 1;
tr[++cot] = -1;
}
sort(tr + 1, tr + cot + 1, cmp);
for (int j = 1; j <= cot; j++) {
if (tr[j] > 0) {
s.push(tr[j]);
}
else {
int now = s.top();
s.pop();
if (now != 1) {
int fa = s.top();
sum[fa] += min(sum[now], mi[now]);
} else {
printf("%lld\n", sum[1]);
}
sum[now] = 0;
book[now] = false;
}
}
}
}
/*
2 5
0 1 1 1 1
0 1 1 2 4
0 2 1 2 1
0 2 1 1 4
*/