虚树

众所周知,虚树是一类重构树,用于处理点数较多而关键点(有效点)数较少的树上问题。举个栗子,我们所熟知的后缀树就是一种虚树……

定义

给定点集 $V_k$ 代表有效点,我们定义一颗树 $T=(V,E)$ 是建立在 $V_k$ 上的虚树,当且仅当:

  1. $V_k\subseteq V$
  2. $\forall x\in V, x\in V_k \text{ or } \exists u,v\in V, \text{s.t. } \text{LCA}(u,v)=x$
  3. $\forall (u,v)\in E, \text{LCA}(u,v)=u\text{ or }v$

一句话来讲:虚数是关键点以及关键点的 LCA 构成的,保证原树的祖孙关系不变的重构树。

构建

模仿笛卡尔树的构建,虚树的构建可以使用单调栈在 $O(|V_k|\log |V|)$ 的时间内完成,其中 $\log V$ 的复杂度是倍增 LCA 的复杂度。如果使用 $O(n)-O(1)$ 的 RMQ-LCA,则可以降至 $O(|V_k|\log |V_k|)$,基本可以视作线性。
这种方法一般被称为「单调栈维护右链」。

顾名思义,这种构建方法的本质就在于使用单调栈去维护虚数最靠右边的树链。容易得出这份代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<algorithm>
using std :: sort;
const int CN = 1e5 + 5;

class fs{} E[CN << 1];
int hd[CN], ecnt = 0; void add(int x, int y, int z) {}

int lca(int u, int v) {}

int a[CN], stk[CN], top = 0, dfn[CN];
bool cmp(int i, int j) {return dfn[i] < dfn[j];} // 按 dfs 序排序
void bd(){
sort(a + 1, a + a[0] + 1, cmp);
stk[top = 1] = 1, hd[1] = 0, ecnt = 0;
for(int i = 1; i <= a[0]; i++){
if(a[i] == 1) continue;
int l = lca(a[i], stk[top]);
if(l ^ stk[top]){
while(dfn[ stk[top - 1] ] > dfn[l]) add(stk[top - 1], stk[top], 0), top--;
if(l ^ stk[top - 1]) hd[l] = 0, add(l, stk[top], 0), stk[top] = l;
else add(l, stk[top], 0), top--;
}
hd[ a[i] ] = 0, stk[++top] = a[i];
}
for(int i = 1; i < top; i++) add(stk[i], stk[i + 1], 0);
}

一道栗题

$n$ 个点的树,边有边权。$q$ 次询问,每次给出 $k_i$ 个关键点,问切断多少边能使得关键点都不与 $1$ 号节点联通,最小化切断的边的边权。
$n,q,\sum k_i\le 10^5$

如果只有一次询问,则可以通过树上 DP 简单求出。注意到 DP 的过程中有效的点只有关键点和它们的 LCA,因此直接建出虚树 DP 即可,时间复杂度 $O(\sum k_i\log n)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define int long long

const int CN = 3e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;

class fs {public: int to,nxt,w; void init(int t,int n,int d) {to = t, nxt = n, w = d;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y,int z) {E[++ecnt].init(y, hd[x], z); hd[x] = ecnt;}

int n, m, mn[CN], dep[CN], fa[CN][21], dfn[CN], idx = 0;

void dfs(int u, int p){ // 预处理
fa[u][0] = p, dep[u] = dep[p] + 1, dfn[u] = ++idx;
for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) mn[v] = min(mn[u], E[k].w), dfs(v, u);}
}
int lca(int x, int y){ // 倍增 LCA
if(dep[x] < dep[y]) swap(x, y);
for(int k = 20; k + 1; k--) if(dep[ fa[x][k] ] >= dep[y]) x = fa[x][k];
if(x ^ y){
for(int k = 20; k + 1; k--) if(fa[x][k] ^ fa[y][k]) x = fa[x][k], y = fa[y][k];
x = fa[x][0];
}
return x;
}

int a[CN], stk[CN], top = 0;
bool cmp(int i, int j) {return dfn[i] < dfn[j];}
void bd(){ // 建立虚树
sort(a + 1, a + a[0] + 1, cmp);
stk[top = 1] = 1, hd[1] = 0, ecnt = 0; // 小心翼翼的初始化
for(int i = 1; i <= a[0]; i++){
if(a[i] == 1) continue;
int l = lca(stk[top], a[i]);
if(l ^ stk[top]){
while(dfn[ stk[top - 1] ] > dfn[l]) add(stk[top - 1], stk[top], 0), top--;
if(l ^ stk[top - 1]) hd[l] = 0, add(l, stk[top], 0), stk[top] = l;
else add(l, stk[top], 0), top--;
}
hd[ a[i] ] = 0, stk[++top] = a[i]; // 小心翼翼的初始化
}
for(int i = 1; i < top; i++) add(stk[i], stk[i + 1], 0);
}

int f[CN]; bool is[CN];
void dp(int u, int p){ // DP
f[u] = mn[u]; int sum = 0; // 小心翼翼的初始化
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to; if(v ^ p) dp(v, u), sum += f[v];
}
if(!is[u]) f[u] = min(f[u], sum);
}

signed main()
{
n = read(); for(int i = 1; i < n; i++) {int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w);}
mn[1] = INF, dfs(1, 0);
for(int k = 1; k <= 20; k++) for(int i = 1; i <= n; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];

memset(hd, 0, sizeof(hd)), ecnt = 0;
m = read();
while(m--){
a[0] = read(); for(int i = 1; i <= a[0]; i++) a[i] = read(), is[ a[i] ] = true;
bd(), dp(1, 0), printf("%lld", f[1]), puts("");
for(int i = 1; i <= a[0]; i++) is[ a[i] ] = false; // 小心翼翼的清空标记
}
}

又一道栗题

$n$ 个点的树,$q$ 次询问,每次给出 $k_i$ 个关键点,问切断多少点能使得关键点互不相连,无解输出 -1。
$n,q,\sum k_i\le 10^5$

依然沿用上题的思路,只不过在树上 DP 的时候细节较多。可以维护一个 $g[u]$ 表示子树 $u$ 中是否还存在与 $u$ 相连的关键点,在转移时分类讨论即可,时间复杂度 $O(\sum k_i\log n)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

const int CN = 1e5 + 5;

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}

int n, q;

int dep[CN], fa[CN][21], dfn[CN], idx = 0;
void dfs(int u, int p){
fa[u][0] = p, dep[u] = dep[p] + 1, dfn[u] = ++idx;
for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) dfs(v, u);}
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
if(u ^ v){
for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k];
u = fa[u][0];
}
return u;
}

int stk[CN], top = 0, a[CN];
bool cmp(int i, int j) {return dfn[i] < dfn[j];}
void bd(){
sort(a + 1, a + a[0] + 1, cmp);
stk[top = 1] = 1, hd[1] = 0, ecnt = 0;
for(int i = 1; i <= a[0]; i++){
if(a[i] == 1) continue;
int l = lca(stk[top], a[i]);
if(l ^ stk[top]){
while(dfn[ stk[top - 1] ] > dfn[l]) add(stk[top - 1], stk[top]), top--;
if(l ^ stk[top - 1]) hd[l] = 0, add(l, stk[top]), stk[top] = l;
else add(l, stk[top]), top--;
}
hd[ a[i] ] = 0, stk[++top] = a[i];
}
for(int i = 1; i < top; i++) add(stk[i], stk[i + 1]);
}

int f[CN], g[CN]; bool is[CN];
bool dp(int u, int p){
f[u] = g[u] = 0; int cnt = 0;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to; if(v == p) continue;
if(!dp(v, u)) return false;
f[u] += f[v], cnt += g[v];
if(is[u] && is[v] && dep[v] - dep[u] <= 1) return false; // 无解
}
if(is[u]) f[u] += cnt, g[u] = 1; // 讨论 u 的决策
else if(cnt > 1) f[u]++;
else if(cnt == 1) g[u] = 1;
return true; // 有解
}

int main()
{
n = read(); for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v), add(v, u);}

dfs(1, 0);
for(int k = 1; k <= 20; k++) for(int i = 1; i <= n; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];

q = read();
while(q--){
a[0] = read(); for(int i = 1; i <= a[0]; i++) a[i] = read(), is[ a[i] ] = true;
bd();
if(dp(1, 0)) printf("%d", f[1]), puts("");
else puts("-1");
for(int i = 1; i <= a[0]; i++) is[ a[i] ] = false;
}
}

双一道栗题

$n$ 个点的树,$q$ 次询问,每次给出 $k_i$ 个关键点,问关键点之间的两两距离和,距离最小值和距离最大值。
$n,q,\sum k_i\le 10^5$

距离最大 / 最小都可以简单维护,对于“距离和”这个问题,有一个常用方法是考虑每条边对答案的贡献。这就跟边有关系了,因此在建立虚树时不能再固定以 $1$ 号节点为根,简单维护一下树根即可,时间复杂度 $O(\sum k_i\log n)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

#define int long long

const int CN = 1e6 + 6;
const int INF = 0x3f3f3f3f3f3f3f3f;

class fs {public: int to,nxt,w; void init(int t,int n,int d) {to = t, nxt = n, w = d;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y,int z) {E[++ecnt].init(y, hd[x], z); hd[x] = ecnt;}

int n, q;

int fa[CN][21], dep[CN], dis[CN], dfn[CN], idx = 0;
void dfs(int u, int p){
fa[u][0] = p, dep[u] = dep[p] + 1, dfn[u] = ++idx;
for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) dis[v] = dis[u] + E[k].w, dfs(v, u);}
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
if(u ^ v){
for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k];
u = fa[u][0];
}
return u;
}

bool cmp(int i, int j) {return dfn[i] < dfn[j];}
int stk[CN], top = 0, a[CN], rt; // rt 维护树根
void bd(){
sort(a + 1, a + a[0] + 1, cmp);
stk[top = 1] = a[1], hd[ a[1] ] = 0, ecnt = 0;
for(int i = 2; i <= a[0]; i++){
int l = lca(stk[top], a[i]);
if(l ^ stk[top]){
while(dfn[ stk[top - 1] ] > dfn[l]) add(stk[top - 1], stk[top], 0), top--;
if(l ^ stk[top - 1]) hd[l] = 0, add(l, stk[top], 0), stk[top] = l;
else add(l, stk[top], 0), top--;
}
hd[ a[i] ] = 0, stk[++top] = a[i];
}
rt = stk[1]; for(int i = 1; i < top; i++) add(stk[i], stk[i + 1], 0);
}

int mn[CN], mx[CN], sz[CN], amn, amx, ans, tmp1[4], tmp2[4]; bool is[CN];
void dp(int u, int p){
if(!hd[u]) return (void)(mn[u] = mx[u] = 0, sz[u] = 1);

mn[u] = INF, mx[u] = sz[u] = 0; int Mn = INF, pMn = INF, Mx = 0, pMx = 0;
for(int k = hd[u]; k; k = E[k].nxt){
int v = E[k].to, d = dis[v] - dis[u]; if(v == p) continue;
dp(v, u);

mn[u] = min(mn[u], mn[v] + d), tmp1[0] = mn[v] + d,
mx[u] = max(mx[u], mx[v] + d), tmp2[0] = mx[v] + d;
sz[u] += sz[v];

ans += d * (a[0] - sz[v]) * sz[v]; // 计算距离和

tmp1[1] = Mn, tmp1[2] = pMn, tmp2[1] = Mx, tmp2[2] = pMx;
sort(tmp1, tmp1 + 3), sort(tmp2, tmp2 + 3, greater<int>());
Mn = tmp1[0], pMn = tmp1[1], Mx = tmp2[0], pMx = tmp2[1];
}

amn = min(amn, Mn + pMn), amx = max(amx, Mx + pMx); // 计算距离最大 最小
if(is[u]) sz[u]++, amn = min(amn, Mn), mn[u] = 0;
}

signed main()
{
n = read(); for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v, 1), add(v, u, 1);}

dfs(1, 0);
for(int k = 1; k <= 20; k++) for(int i = 1; i <= n; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];

q = read();
while(q--){
a[0] = read(); for(int i = 1; i <= a[0]; i++) a[i] = read(), is[ a[i] ] = true;
bd(), amn = INF, amx = ans = 0; if(a[0] == 1) ans = amn = amx = 0;
dp(rt, 0), printf("%lld %lld %lld", ans, amn, amx), puts("");
for(int i = 1; i <= a[0]; i++) is[ a[i] ] = false;
}
}

相关题目

  1. 「SDOI2011」消耗战
  2. 「CF613D」Kingdom and its Cities
  3. 「HEOI2014」大工程

习题
「HNOI2014」世界树

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×