虚树

虚树

问题引入

在一类树上动态规划问题中,题目中给出的询问往往包含树上的很多节点, 但保证节点的总规模小于一个数值.

如果直接在整颗树上\(\text{dp}\)复杂度和询问次数相关, 这是我们无法接受的. 我们可以找到一种方法使得时间复杂度之和询问节点数有关, 这就非常优秀了.

虚树就这么诞生了.

虚树概念

虚树是只包含给出关键点和关键点两两\(\text{lca}\)的树, 相当于直接压缩了一些无用的路径.

引理一

树上\(n\)个点两两之间的不同\(\text{lca}\)最多有\(\text{n-1}\)

证明一

回忆一下求\(\text{ST}\)表求\(\text{lca}\)的过程, 相当于在一个序列上求一个区间的最小值. 相当与给定序列上的\(n\)个点, 求其两两组成的区间的不同的最小值有多少个. 显然最坏的情况就是每一个由相邻的两个点组成的区间的最小值都不同, 这样最坏也只有\(\text{n-1}\)个不同的最小值

性质很优美啊, 相当于建出来的虚树的点数的规模和关键的规模是相同的

举个栗子

原树:

包含关键点\(\text{1,3,7,8}\)的虚树:

(上面两张图是蒯过来的)

其中\(\text{6}\)\(\text{7,8}\)\(\text{lca}\).

虚树构造

我们维护一个栈, 这个栈从栈底到栈顶的元素对应了一条链上深度由浅到深的点.(这条链不会折)

通常的我们先将所有的关键点按照\(\text{dfs}\)序排序. 然后依次加入栈中, 可能会遇到以下情况:

(设栈为\(\text{st}\), 当前加入的点为\(\text{x}\))

  1. 栈为空, 直接\(\text{st.push(x)}\)就好了.
  2. \(\text{lca(st.top(),x)=st.top()}\), 说明这条链还在延伸, 直接\(\text{st.push(x)}\).
  3. \(\text{lca(st.top(),x)}\ne\text{st.top()}\), 说明\(\text{x}\)\(\text{st.top()}\)分别属于不同的子树, 并且\(\text{st.top()}\)所在的子树已经构造完毕了.我们直接将属于\(\text{st.top()}\)的子树并且在栈中的点都\(\text{pop()}\)掉, 如果其\(\text{lca}\)不在栈中, 也要加入它们两的\(\text{lca}\), 然后再加\(\text{st.push(x)}\).

关键代码:

1
2
3
4
5
6
7
8
9
inline void push(int x) {
tmp.push_back(x);
if(stop == 1) return (void)(st[++stop] = x);
int lca = LCA(x, st[stop]);
if(lca == st[stop]) return (void)(st[++stop] = x);
while(stop > 1 && pos[st[stop - 1]] >= pos[lca]) add(st[stop], st[stop - 1], E), stop--;
if(st[stop] != lca) add(st[stop], lca, E), st[stop] = lca, tmp.push_back(lca);
return (void)(st[++stop] = x);
}

虚树例题

消耗战

先考虑直接\(\text{dp}\), 设\(f[i]\)表示使得\(i\)的子树(不包括\(i\))和根节点不连通的最小花费. 设\(mn[i]\)表示\(i\)到根节点中的最小边权.则有转移: \[ f[i] = \min(mn[i], \sum_{v \in son_i}f[v]) \] 建出虚树后, \(\text{dp}\)转移是一样的.

代码:

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) (int)(x.size())

using namespace std;

typedef long long ll;

const int maxn = 5e5 + 5;

int n, Q, point[maxn];
vector<pair<int, int> > G[maxn];
vector<int> E[maxn];

int fa[maxn], top[maxn], son[maxn], dfn[maxn], dep[maxn], pos[maxn], size[maxn];
ll mn[maxn];
bool vis[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

inline void add(int x, int y) { E[x].push_back(y); E[y].push_back(x); }

inline void dfs(int x) {
size[x] = 1; dfn[++dfn[0]] = x;
pos[x] = dfn[0];
rep(i, 0, SIZE(G[x]) - 1) {
int v = G[x][i].first;
if(v == fa[x]) continue;
mn[v] = min(mn[x], 1ll * G[x][i].second);
fa[v] = x; dep[v] = dep[x] + 1;
dfs(v); size[x] += size[v];
if(size[v] > size[son[x]]) son[x] = v;
}
if(son[x] == 0) son[x] = x;
}

inline int LCA(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
} return dep[x] > dep[y] ? y : x;
}

int st[maxn], stop;

inline void push(int x) {
if(stop == 1) return (void)(st[++stop] = x);
int lca = LCA(x, st[stop]);
// cerr << "LCA = " << lca << endl;
if(lca == st[stop]) return;
while(stop > 1 && pos[st[stop - 1]] >= pos[lca]) add(st[stop - 1], st[stop]), stop--;
if(lca != st[stop]) add(lca, st[stop]), st[stop] = lca;
st[++stop] = x;
}

inline ll dp(int x, int fr, ll sum = 0) {
rep(i, 0, SIZE(E[x]) - 1) {
int v = E[x][i];
if(v == fr) continue;
sum += dp(v, x);
} E[x].clear();
return vis[x] ? mn[x] : min(mn[x], sum);
}

int main() {
// freopen("1.in", "r", stdin);
n = read();
rep(i, 1, n - 1) {
int x = read(), y = read(), w = read();
G[x].push_back(make_pair(y, w));
G[y].push_back(make_pair(x, w));
}
memset(mn, 0x3f, sizeof(mn));
dfs(1);
rep(i, 1, n) top[dfn[i]] = dfn[i] == son[fa[dfn[i]]] ? top[fa[dfn[i]]] : dfn[i];
Q = read();
rep(i, 1, Q) {
int k = read();
rep(i, 1, k) vis[point[i] = read()] = 1;
sort(point + 1, point + 1 + k, [](int x, int y) -> bool { return pos[x] < pos[y]; });
st[stop = 1] = 1;
rep(i, 1, k) push(point[i]);
while(stop > 1) add(st[stop - 1], st[stop]), stop--;
// cerr << mn[10] << " " << mn[6] << endl;
printf("%lld\n", dp(1, 1));
rep(i, 1, k) vis[point[i]] = 0;
}
return 0;
}

世界树

建出虚树后. 将所有的关键点作为起点做一遍\(\text{Dijkstra}\)求出到其他不是关键点的点最小距离.

但问题在于因为我们压缩了路径, 所以虚树上两个点之间在原树上其实是有点的, 我们枚举虚树上的一条边\(\text{(u,v)}\), 可以通过到两个端点最小距离和边权算出来这条边上的分界点\(\text{x}\). 然后求一下\(\text{(u,x)}\)\(\text{(x,v)}\)这两条路径上的点的\(\text{size}\)和, 就可以统计答案了.

代码:

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) (int)(x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define dis(x, y) (abs(dep[x] - dep[y]))

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 5;
const int inf = 0x3f3f3f3f;

int n, q, m, point[maxn], vis[maxn], Z[maxn], Ans;
vector<int> G[maxn], tmp;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int head[maxn], cnt = 1;
struct Graph {
int fr, to, nt, w;
Graph(int a = 0, int b = 0, int c = 0, int d = 0) { to = a; nt = b; w = c; fr = d; }
} e[maxn << 1];

int dfn[maxn], pos[maxn], size[maxn], fa[maxn][20], stop, st[maxn], dep[maxn];

inline void add(int x, int y, vector<int> *G) { G[x].pb(y); G[y].pb(x); }
inline void ini(int x, int y, int w) { e[++cnt] = Graph(y, head[x], w, x); head[x] = cnt; }
inline void add(int x, int y) { ini(x, y, dis(x, y)); ini(y, x, dis(x, y)); }

inline void dfs(int x) {
size[x] = 1; dfn[++dfn[0]] = x;
pos[x] = dfn[0];
for(int i = 1; dep[x] >> i; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(auto v : G[x]) {
if(v == fa[x][0]) continue;
dep[v] = dep[x] + 1; fa[v][0] = x;
dfs(v);
size[x] += size[v];
}
}

inline int Jump(int x, int d) {
for(int i = 0; d; d >>= 1, i++) if(d & 1) x = fa[x][i];
return x;
}

inline int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
x = Jump(x, dep[x] - dep[y]);
if(x == y) return x;
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];
}

inline void push(int x) {
tmp.push_back(x);
if(stop == 1) return (void)(st[++stop] = x);
int lca = LCA(x, st[stop]);
if(lca == st[stop]) return (void)(st[++stop] = x);
while(stop > 1 && pos[st[stop - 1]] >= pos[lca]) add(st[stop], st[stop - 1]), stop--;
if(lca != st[stop]) add(st[stop], lca), st[stop] = lca, tmp.push_back(lca);
return (void)(st[++stop] = x);
}

inline void Solve(int m) {
static int dis[maxn], ans[maxn], bel[maxn], inq[maxn], siz[maxn];
priority_queue<pair<int, int> > q; Ans = 0;
for(int u : tmp) {
dis[u] = inf, ans[u] = inq[u] = bel[u] = 0;
siz[u] = size[u];
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to;
if(pos[v] >= pos[u]) siz[u] -= size[Jump(v, dep[v] - dep[u] - 1)];
}
// cerr << "siz[" << u << "] = " << siz[u] << endl;
}
rep(i, 1, m) bel[point[i]] = point[i], q.push(make_pair(dis[point[i]] = 0, point[i]));
while(q.size()) {
int u = q.top().second; q.pop();
if(inq[u]) continue; inq[u] = 1;
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to, w = e[i].w;
if(dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
bel[v] = bel[u];
q.push(make_pair(-dis[v], v));
// cerr << "trans1 : " << u << " -> " << v << endl;
} else if(dis[v] == dis[u] + w) {
bel[v] = min(bel[v], bel[u]);
// cerr << "trans2 : " << u << " -> " << v << endl;
}
}
}
for(int u : tmp) ans[bel[u]] += siz[u];
// rep(i, 1, m) printf("preans[%d] = %d\n", point[i], ans[point[i]]);
for(int i = 1; i <= cnt; i += 2) if(e[i].w > 1) {
int a = e[i].fr, b = e[i].to, x = 0;
if(bel[a] > bel[b]) swap(a, b);
// cerr << "---------------------" << endl;
// cerr << "a = " << a << ", b = " << b << endl;
//if(e[i].w & 1) x = (e[i].w - 1 + dis[b] - dis[a]) / 2;
//else
x = (e[i].w + dis[b] - dis[a]) / 2;
x = max(x, 0); x = min(x, e[i].w - 1);
// FBI Warning : should be ceiled
// cerr << "x = " << x << endl;
if(pos[a] < pos[b]) {
int u = Jump(b, e[i].w - x - 1), son = Jump(b, e[i].w - 1);
ans[bel[a]] += size[son] - size[u];
ans[bel[b]] += size[u] - size[b];
} else {
int u = Jump(a, x), son = Jump(a, e[i].w - 1);
ans[bel[b]] += size[son] - size[u];
ans[bel[a]] += size[u] - size[a];
}
}
rep(i, 1, m) printf("%d ", ans[Z[i]]), Ans += ans[Z[i]];
// putchar('\n');
printf("\n");
// cerr << Ans << endl;
for(int u : tmp) head[u] = 0; cnt = 1;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n - 1) add(read(), read(), G);
dfs(1); q = read();
while(q--) {
// cerr << "----------------------" << endl;
m = read(); tmp.clear(); tmp.push_back(1);
rep(i, 1, m) Z[i] = point[i] = read();
sort(point + 1, point + 1 + m, [](int x, int y) -> bool { return pos[x] < pos[y]; });
int p = 1; if(point[p] == 1) st[stop = 1] = point[p++];
if(p == 1) st[stop = 1] = 1;
rep(i, p, m) push(point[i]);
while(stop > 1) add(st[stop], st[stop - 1]), stop--;
Solve(m);
}
return 0;
}
/*
*/

大工程

  1. 直接换根\(\text{dp}\), 是个很经典的问题啊
  2. 普及组\(\text{dp}\)?
  3. 直径?

注意到后两问的选择的端点不能是关键点的\(\text{lca}\).

所以这道题就是想考你虚树怎么建吗??很迷啊.

代码:

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) (int)(x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define dis(x, y) (abs(dep[x] - dep[y]))

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;

int n, q, m, point[maxn], Z[maxn];
vector<int> G[maxn], tmp;
vector<pair<int, int> > E[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int dfn[maxn], pos[maxn], size[maxn], top[maxn], son[maxn], fa[maxn], dep[maxn], st[maxn], stop;

inline void add(int x, int y, vector<int> *G) { G[x].push_back(y); G[y].push_back(x); }
inline void add(int x, int y, vector<pair<int, int> > *G) { G[x].pb(mp(y, dis(x, y))); G[y].pb(mp(x, dis(x, y))); }

inline void dfs(int x) {
size[x] = 1; dfn[++dfn[0]] = x;
pos[x] = dfn[0];
for(auto v : G[x]) {
if(v == fa[x]) continue;
dep[v] = dep[x] + 1; fa[v] = x;
dfs(v);
size[x] += size[v];
if(size[v] > size[son[x]]) son[x] = v;
}
}

inline int LCA(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
} return dep[x] > dep[y] ? y : x;
}

inline int Dis(int x, int y) { return dep[x] + dep[y] - 2 * dep[LCA(x, y)]; }

int siz[maxn], vis[maxn], AnsMn, AnsMx, f[maxn][2], g[maxn][2];
ll dis[maxn], Ans, sw[maxn], ans;

inline void push(int x) {
tmp.push_back(x);
if(stop == 1) return (void)(st[++stop] = x);
int lca = LCA(x, st[stop]);
if(lca == st[stop]) return (void)(st[++stop] = x);
while(stop > 1 && pos[st[stop - 1]] >= pos[lca]) add(st[stop], st[stop - 1], E), stop--;
if(st[stop] != lca) add(st[stop], lca, E), st[stop] = lca, tmp.push_back(lca);
return (void)(st[++stop] = x);
}

inline void dfs(int x, int fr) {
siz[x] = vis[x]; dis[x] = 0;
f[x][0] = f[x][1] = 0;
g[x][0] = g[x][1] = inf;
if(vis[x]) ans += dep[x];
for(auto v : E[x]) {
if(v.first == fr) continue;
dfs(v.first, x);
siz[x] += siz[v.first];
dis[x] += dis[v.first] + 1ll * siz[v.first] * v.second;
if(f[v.first][1] + v.second > f[x][1]) {
f[x][0] = f[x][1];
f[x][1] = f[v.first][1] + v.second;
} else f[x][0] = max(f[x][0], f[v.first][1] + v.second);
if(vis[v.first]) {
if(v.second < g[x][0]) g[x][1] = g[x][0], g[x][0] = v.second;
else g[x][1] = min(g[x][1], v.second);
}
if(g[v.first][0] + v.second < g[x][0]) {
g[x][1] = g[x][0];
g[x][0] = g[v.first][0] + v.second;
} else g[x][1] = min(g[x][1], g[v.first][0] + v.second);
}
if(f[x][0] && f[x][1]) AnsMx = max(AnsMx, f[x][0] + f[x][1]);
AnsMn = min(AnsMn, g[x][1] + g[x][0]);
if(vis[x]) AnsMx = max(AnsMx, f[x][1]), AnsMn = min(AnsMn, g[x][0]);
// cerr << "g[" << x << "][0] = " << g[x][0] << endl;
// cerr << "g[" << x << "][1] = " << g[x][1] << endl;
// cerr << "dis[" << x << "] = " << dis[x] << endl;
}

inline void rdp(int x, int fr, ll sum) {
// cerr << "sum[" << x << "] = " << sum << endl;
if(vis[x]) Ans += sum + dis[x];
for(auto v : E[x]) {
if(v.first == fr) continue;
rdp(v.first, x, sum + 1ll * v.second * (siz[1] - 2 * siz[v.first]) + dis[x] - dis[v.first]);
}
}

inline void Solve() {
AnsMn = inf; AnsMx = -inf; Ans = 0; ans = 0;
dfs(1, 1);
// for(int i : tmp) cerr << "dis[" << i << "] = " << dis[i] << endl;
// cerr << ans << " " << dis[1] << endl;
rdp(1, 1, 0);
// cerr << m << " " << siz[1] << endl;
printf("%lld %d %d\n", Ans / 2, AnsMn, AnsMx);
for(int i : tmp) E[i].clear();
for(int i = 1; i <= m; i++) vis[point[i]] = 0;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n - 1) add(read(), read(), G);
dfs(1);
rep(i, 1, dfn[0]) top[dfn[i]] = dfn[i] == son[fa[dfn[i]]] ? top[fa[dfn[i]]] : dfn[i];
cerr << Dis(3, 4) + Dis(3, 5) + Dis(4, 5) << endl;
q = read();
while(q--) {
// cerr << "-----------------" << endl;
m = read(); tmp.clear(); tmp.push_back(1);
rep(i, 1, m) vis[Z[i] = point[i] = read()] = 1;
sort(point + 1, point + 1 + m, [](int x, int y) -> bool { return pos[x] < pos[y]; });
// cerr << m << endl;
// rep(i, 1, m) cerr << "point[" << i << "] = " << point[i] << endl;
int p = 1; if(point[p] == 1) st[stop = 1] = point[p++];
if(p == 1) st[stop = 1] = 1;
rep(i, p, m) push(point[i]);
while(stop > 1) add(st[stop], st[stop - 1], E), stop--;
Solve();
}
return 0;
}
/*
*/