【学习笔记】虚树学习&做题笔记

捣鼓了捣鼓虚树,发现原来难点在DP

发现了网上一个 QQ 表情的 CDN,感觉很可爱w。

虚树学习笔记

大概就是一种快速维护关键点信息的方式。具体思想可以看做缩点(链),对于 $k$ 个关键点,虚树可以将问题规模缩小至 $O(k)$ 而不是 $O(n)$ 。

建树方式比较直观,跟笛卡尔树一样是维护右链,但是由于孩子可能很多所以建树方式比笛卡尔树要复杂。值得一提的是,虚树都是在退栈的时候才会连边,并且虚树建立时需要考虑的主要矛盾就是 LCA 的取舍,因为维护关键点仍然需要保持其树形结构。

考虑整棵虚树把 $0$ 号点作为虚根 $root$,将关键点按照 dfn 从小到大排序。每次插入一个点,会首先判断两个 case:

0、如果此时不是新的一条链,直接将当前点入栈。

1、如果此时是新的一条链,那么把所有深度比当前点大的点都出栈,类似一个 lower_bound 的过程,保留到「左链中第一个深度比当前点更深的点 $t$」为止。之后考虑如果当前元素与原来的栈顶元素 $s$ 的 LCA,设为 $o$, 不是 $t$,那么就连边(o,t)$ 和该把 $t$ 出栈、 $o$ 入栈。

过程的充分性和合法性是显然的。最后不要忘记栈中剩下的最右链。这个地方 xls 在洛谷上放了个板子,但是数据可能不是很强,但我觉得这似乎也没必要很强:戳我

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

namespace virtual_tree{
int cnt ;
int sz[N] ;
int fa[N]
int nfa[N] ;
int dep[N] ;
int dfn[N] ;
int son[N] ;
int top[N] ;
int stk[N], tp ;
vector <int> a, T ;
void dfs1(int x, int da){
dep[x] = dep[da] + 1 ;
sz[x] = 1, fa[x] = da ;
for (auto y : E[x]){
if (y == da) continue ;
dfs1(y, x) ; sz[x] += sz[y] ;
if (sz[y] > sz[son[x]]) son[x] = y ;
}
}
void dfs2(int x, int tp){
top[x] = tp ;
dfn[x] = ++ cnt ;
if (son[x])
dfs2(son[x], tp) ;
for (auto y : E[x])
if (y != fa[x] && y != son[x]) dfs2(y, y) ;
}
int lca(int x, int y){
if (!y) return 0 ;
while (top[x] != top[y]){
if (dep[top[x]] < dep[top[y]])
std :: swap(x, y) ; x = fa[top[x]] ;
}
if (dep[x] > dep[y])
std :: swap(x, y) ; return x ;
}
void ins(){
sort(a.begin(), a.end(), [](int x, int y){ return dfn[x] < dfn[y] ; }) ;
for (auto x : a){
int z = lca(x, stk[tp]) ;
if (z != stk[tp]){
while (tp && dep[stk[tp - 1]] >= dep[z])
nfa[stk[tp]] = stk[tp - 1], -- tp ; //类似 lower_bound
if (stk[tp] != z) nfa[stk[tp]] = z, stk[tp] = z ;
}
stk[++ tp] = x ;
}
while (tp) nfa[stk[tp]] = stk[tp - 1], -- tp ;
}
}

然后以后就管虚树上的关键点叫做「纯虚点」,那些 LCA 叫做「半虚点」好了。

虚树练习笔记

[SDOI2011] 消耗战

多组询问。每次给出一些树上关键点,边带权,求使这些点均不与根节点连通的最小代价。

考虑建出虚树之后变成了裸 DP。设 $f_i$ 为搞完 $i$ 子树内的所有关键点的最小代价,那么有转移

其中 $val(root\to i)$ 是根节点到 $i$ 的边权最大值,$c_i$ 表示 $i$ 是否为关键点,转移就好了。

「My-Code」
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
void add_e(int x, int y){ T[y].p_b(x) ; }
void clear(int x){
for (auto y : T[x]) clear(y) ;
T[x].clear() ; vis[x] = 0 ; f[x] = 0 ;
}
void ins(){
sort(a.begin(), a.end(), [](int x, int y){ return dfn[x] < dfn[y] ; }) ;
for (auto x : a){
int z = lca(x, stk[tp]) ;
if (z != stk[tp]){
while (tp && dep[stk[tp - 1]] >= dep[z])
add_e(stk[tp], stk[tp - 1]), -- tp ;
if (stk[tp] != z) add_e(stk[tp], z), stk[tp] = z ;
}
stk[++ tp] = x ;
}
while (tp)
add_e(stk[tp], stk[tp - 1]), -- tp ;
}
void solve(int x){
ll tmp = 0 ;
// printf("%d\n", x) ;
for (auto y : T[x]){
solve(y) ;
tmp += f[y] ;
}
if (!T[x].size() || vis[x])
tmp = I ; f[x] = min(val[x], tmp) ;
// printf("%d %lld\n", x, f[x]) ;
}

[GZOI2017]共享单车

求出这个图的最短路径生成树后,树上每个点初始颜色为 $0$ 。有两种操作:

1、将部分点颜色取反

2、给出一些点,建出虚树(边权为两点树上距离),求最小割边代价使得虚树上没有颜色为 $1$ 的点与根联通。

这题是个十分没意思的读题题+二合一题。感觉非要求出最短路树来就是多此一举。然后他这题十分有意思的一点就是明确告诉你了这是棵虚树,也就是默认树上全部的点都是纯虚点。然后 DP 过程就是消耗战。

「My-Code」
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
int rt ;
int col[N] ;
int n, m, Q, k ;

int dis[N] ;
int pre[N] ;
int prev[N] ;
bool vis[N] ;
queue <int> q ;

void spfa(){
memset(dis, 63, sizeof(dis)) ;
q.push(rt) ; vis[rt] = 1 ; dis[rt] = 0 ;
while (!q.empty()){
int x = q.front() ;
q.pop() ; vis[x] = 0 ;
for (auto t : E[x]){
if (dis[t.fr] > dis[x] + t.sc){
dis[t.fr] = dis[x] + t.sc ;
pre[t.fr] = x, prev[t.fr] = t.sc ;
if (!vis[t.fr])
q.push(t.fr), vis[t.fr] = 1 ;
}
}
}
for (int i = 1 ; i <= n ; ++ i) E[i].clear() ;
}
void solve(int x){
int res = 0 ;
// printf("%d\n", x) ;
if (x == rt) val[x] = I ;
for (auto y : T[x]){
val[y.fr] = min(val[x], y.sc) ;
solve(y.fr) ; res += f[y.fr] ;
}
if (col[x]) res = I ;
f[x] = min(res, val[x]) ;
// printf("#%d %d %d\n", x, val[x], f[x]) ;
}


int main(){
int x, y, z ;
n = qr(), m = qr() ;
rt = qr(), Q = qr() ;
for (int i = 1 ; i <= m ; ++ i){
x = qr(), y = qr(), z = qr(),
E[x].p_b(m_k(y, z)), E[y].p_b(m_k(x, z)) ;
}
spfa() ; val[rt] = val[0] = I ;
for (int i = 1 ; i <= n ; ++ i)
if (pre[i]) E[pre[i]].p_b(m_k(i, prev[i])) ;
dep[rt] = 1, dfs1(rt), dfs2(rt, rt) ;
// for (int i = 1 ; i <= n ; ++ i) printf("%d %d\n", i, prev[i]) ;
while (Q --){
z = qr() ; k = qr() ;
if (!z){
for (int i = 1 ; i <= k ; ++ i) col[qr()] ^= 1 ;
}
else {
a.clear() ; col[rt] = 0 ;
for (int i = 1 ; i <= k ; ++ i) a.p_b(y = qr()), g[y] = 1 ;
ins() ; solve(0) ; printf("%d\n", f[0] ? f[0] : -1) ; clear(0) ;
}
}
return 0 ;
}

[BOI 2017] Railway

给出一棵 $n$ 个节点的树。有 $m$ 次染色操作,每次操作给出一些点,把覆盖他们的最小连通块内的边染上颜色。求被染色次数不小于 $k$ 的边数。

大概是考察了虚树的一个性质,就是虚树一定可以使得关键点之间的路径长度以最短的方式连边(这似乎应该是树的性质)。然后就是求一遍虚树然后差分一下就好了。

一个小彩蛋,一开始尝试对 dfn 排序直接对临点取 LCA 打 tag 发现并不对 x,我可能是智障了。

「My-Code」
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

int do_tag(int x, int y){
// printf("%d %d\n", x, y) ;
tag[x] ++, tag[y] -- ;
}
bool comp(int x, int y){
return dfn[x] < dfn[y] ;
}
int tot ;
int ans[N] ;
void dfs(int x){
// printf("%d\n", x) ;
for (auto y : T[x]){
if (x)
do_tag(y, x) ;
dfs(y) ;
}
T[x].clear() ;
}
void solve(int x){
for (auto y : E[x]){
if (y.fr == fa[x]) continue ;
solve(y.fr) ; tag[x] += tag[y.fr] ;
}
if (tag[x] >= k) ans[++ tot] = x ;
}

[SDOI 2015] 寻宝游戏

没找到简化题面,咕了咕了。

这似乎跟虚树没啥关系,又似乎有啥关系。本质上是要求在关键点变化时维护虚树的权和,那么发现可以直接拿个 set 维护 dfn。有点小小的细节。

「My-Code」
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
int n, m ;

bool vis[N] ;

set <int> s ;

using namespace virtual_tree ;

ll calc(int x, int y){
if (!y) return 0 ;
x = Id[x] ; y = Id[y] ;
return val[x] + val[y] - (val[lca(x, y)] << 1) ;
}

int main(){
int x, y, z, p, q ;
scanf("%d%d", &n, &m) ;
for (int i = 1 ; i < n ; ++ i){
x = qr(), y = qr(), z = qr() ;
E[y].p_b(mk(x, z)), E[x].p_b(mk(y, z)) ;
}
dfs1(1, 0) ;
dfs2(1, 1) ;
while (m --){
x = qr() ;
y = dfn[x] ;
if (vis[x])
s.erase(y) ;
else s.insert(y) ;
auto f = s.lower_bound(y) ;
auto g = s.upper_bound(y) ;
q = *(g == s.end() ? s.begin() : g) ;
p = *(f == s.begin() ? -- s.end() : -- f) ;
// printf("%d %d\n", p, q) ;
if (vis[x]){
vis[x] = 0 ;
ans -= calc(y, p) + calc(y, q) - calc(p, q) ;
}
else {
vis[x] = 1 ;
ans += calc(y, p) + calc(y, q) - calc(p, q) ;
}
printf("%lld\n", ans) ;
}
return 0 ;
}

[HEOI2014] 大工程

国家有一个大工程,要给一个非常大的交通网络里建一些新的通道。

我们这个国家位置非常特殊,可以看成是一个单位边权的树,城市位于顶点上。

在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。

现在国家有很多个计划,每个计划都是这样,我们选中了 k 个点,然后在它们两两之间 新建 C(k,2)条 新通道。现在对于每个计划,我们想知道: 1.这些新通道的代价和 2.这些新通道中代价最小的是多少 3.这些新通道中代价最大的是多少。

不难发现只要预处理了虚树上点之间的边权和就比较简单了。考虑第一问就只需要算每条边的贡献,第三问就只需要维护一个最大值一个次大值就好了。然后第二问挂了好几次,因为一开始觉得这个只要取 dfs 序相邻的点就一定最优…然后就人没了。大概最小值就需要维护一个最近的纯虚点到自己的距离,然后根据纯虚和半虚分类讨论一波就好了。

「My-Code」
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
int dis(int a, int b){
if (!b) return 0 ;
return dep[a] + dep[b] - (dep[lca(a, b)] << 1) ;
}
void add_e(int x, int y){
T[y].p_b(m_k(x, dis(x, y))) ;
}
void clear(int x){
for (auto y : T[x]) clear(y.fr) ;
T[x].clear() ; f[x] = g[x] = h[x] = 0 ;
}
void ins(){
sort(a.begin(), a.end(), [](int x, int y){ return dfn[x] < dfn[y] ; }) ;
for (auto x : a){
int z = lca(x, stk[tp]) ;
if (z != stk[tp]){
while (tp && dep[stk[tp - 1]] >= dep[z])
add_e(stk[tp], stk[tp - 1]), -- tp ;
if (stk[tp] != z) add_e(stk[tp], z), stk[tp] = z ;
}
stk[++ tp] = x ;
}
while (tp)
add_e(stk[tp], stk[tp - 1]), -- tp ;
}
void dopre(int x){
int mk = g[x], z ;
int y, v = I, res = 0 ;
for (auto t : T[x]){
y = t.fr ;
dopre(y) ;
g[x] += g[y] ;
z = dis(x, h[y]) ;
ans3 = min(ans3, v + z) ;
if (z < v)
v = z, h[x] = h[y] ;
ans2 = max(ans2, f[y] + t.sc + res) ;
res = max(res, f[y] + t.sc) ;
}
if (mk)
ans3 = min(ans3, v), h[x] = x ;
f[x] = res ;
}
void solve(int x){
int y ;
for (auto t : T[x]){
y = t.fr ; solve(y) ;
ans1 += 1ll * t.sc * (sum - g[y]) * g[y] ;
}
}

CF613D Kingdom and its Cities

一个王国有 n 座城市,城市之间由 n-1条道路相连,形成一个树结构,国王决定将一些城市设为重要城市。

这个国家有的时候会遭受外敌入侵,重要城市由于加强了防护,一定不会被占领。而非重要城市一旦被占领,这座城市就不能通行。

国王定了若干选择重要城市的计划,他想知道,对于每个计划,外敌至少要占领多少个非重要城市,才会导致重要城市之间两两不连通。如果外敌无论如何都不可能导致这种局面,输出 -1。

惨遭降智.png

感觉这题细节推起来有点烦人,主要考察了细心讨论的能力。直接放代码吧。唯一需要注意的地方就是如果子树内只有一个关键点,可以选择暂时不割,留到以后。

1
2
3
4
5
6
7
8
9
10
11
void solve(int x){
int re = 0 ;
for (auto y : T[x]){
solve(y) ;
re += g[y], f[x] += f[y] ;
}
if (vis[x])
f[x] += re, g[x] = 1 ;
else if (re > 1) f[x] ++ ;
else if (re == 1) g[x] = 1 ;
}