发表更新OI笔记16 分钟读完 (大约2413个字)

虚树

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

定义

给定点集 $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」世界树

虚树

https://big-news.cn/2020/09/11/虚树/

作者

ce-amtic

发布于

2020-09-11

更新于

2020-12-27

许可协议

CC BY-NC-SA 4.0

#

评论

目录

推荐阅读

Your browser is out-of-date!

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

×

×