集训 Day 3 总结 虚树 + dfs tree + 基环树

虚树

虚树，顾名思义是 只关注原树上的某些 关键点，在保留原树祖孙关系的前提下建出的一棵边数、点数大大减少的树

适用于优化某些在整棵树上进行 $dp$、$dfs$ 的问题

通常是题目中出现多次询问，每次给出树上的一些关键点，同时保证 $\sum 关键点数\le n$ ，很大可能就是建出虚树来处理

概括来说，虚树只进行两步操作 剪掉无用树枝 和 压缩树上路径

Warning

有一个常见误区：压缩树上路径 的含义

如图 ，只有红色是关键点，黑色加粗为虚树上的点

若是只压缩路径，那么完全可以 $1->4，1->6$ 连边 ，而不需要保留 $4,6$ 的 lca $3$ 号点

为什么要这样保留呢？实际上，这保证了 虚树上的边对应原树上的路径是不交的

这个性质在后面题目中有大用

思想懂了，来看具体实现

build 建树

通常有两种建树方式，两次 $sort$ 和 单调栈

本人通常采用前者，码量较短

int p[2*N] , rt , len , num ;
void build( int x )
{
	sort( c[x].begin() , c[x].end() , cmp ) ;
	num = c[x].size() ;
	len = 0 ;
	p[++len] = c[x][0] ;
	for(int i = 1 ; i < c[x].size() ; i ++ ) {
		p[++len] = c[x][i] ;
		p[++len] = LCA( c[x][i-1] , c[x][i] ) ; // 由虚树定义，这样一定能把虚树上的点都包含 
	}
	sort( p+1 , p+len+1 , cmp ) ;
	len = unique( p+1 , p+len+1 ) - (p+1) ; // 再去重 
	for(int i = 2 ; i <= len ; i ++ ) { // 恰好连了 len-1 条边，且不重复，不成环 
		int x = p[i] , y = LCA( x , p[i-1] ) ;
		add( y , x , dep[x]-dep[y] ) ;
	}
	rt = p[1] ;
}

基于 $dfs$ 序的性质，可以保证建出的虚树是正确的，需要注意 $p$ 数组需要开 $2$ 倍

从代码里我们也可以得到 虚树上的点数上界为关键点的 2 倍，是线性级别

例题

A

To
直接在原树上跑 $n$ 次 $dfs$ 显然会超时

所以建出虚树后直接 $dfs$ 统计即可

#include<bits/stdc++.h>
using namespace std ;

typedef long long LL ;
const int N = 2e5 + 100 ; 

int n , a[N] ;
vector<int> E[N] , c[N] ;

int dep[N] , fat[N][22] , dfn[N] , tim ;
void dfs( int x , int fa )
{
	dep[x] = dep[fa] + 1 , fat[x][0] = fa , dfn[x] = ++tim ; 
	for(int i = 1 ; i <= 20 ; i ++ ) fat[x][i] = fat[fat[x][i-1]][i-1] ;
	for(int t : E[x] ) {
		if( t == fa ) continue ;
		dfs( t , x ) ;
	}
}
int LCA( int x , int y )
{
	if( dep[x] < dep[y] ) swap( x , y ) ;
	for(int i = 20 ; i >= 0 ; i -- ) {
		if( dep[fat[x][i]] >= dep[y] ) x = fat[x][i] ;
	}
	if( x == y ) return x ;
	for(int i = 20 ; i >= 0 ; i -- ) {
		if( fat[x][i] != fat[y][i] ) x = fat[x][i] , y = fat[y][i] ;
	}
	return fat[x][0] ;
}
bool cmp ( int x , int y )
{
	return dfn[x] < dfn[y] ;
}

struct nn
{
	int lst , to , val ;
}e[N] ;
int head[N] , tot ;
inline void add( int x , int y , int v )
{
	e[++tot] = (nn){ head[x] , y , v } ;
	head[x] = tot ;
}
int p[2*N] , rt , len , num ;
void build( int x )
{
	sort( c[x].begin() , c[x].end() , cmp ) ;
	num = c[x].size() ;
	len = 0 ;
	p[++len] = c[x][0] ;
	for(int i = 1 ; i < c[x].size() ; i ++ ) {
		p[++len] = c[x][i] ;
		p[++len] = LCA( c[x][i-1] , c[x][i] ) ; // 由虚树定义，这样一定能把虚树上的点都包含 
	}
	sort( p+1 , p+len+1 , cmp ) ;
	len = unique( p+1 , p+len+1 ) - (p+1) ; // 再去重 
	for(int i = 2 ; i <= len ; i ++ ) { // 恰好连了 len-1 条边，且不重复，不成环 
		int x = p[i] , y = LCA( x , p[i-1] ) ;
		add( y , x , dep[x]-dep[y] ) ;
	}
	rt = p[1] ;
}
LL ans ;
int siz[N] , col ;
void calc( int x , int fa )
{
	if( a[x] == col ) siz[x] = 1 ;
	else siz[x] = 0 ;
	for(int i = head[x] ; i ; i = e[i].lst ) {
		int t = e[i].to ;
		if( t == fa ) continue ;
		calc( t , x ) ;
		siz[x] += siz[t] ;
		ans += 1LL*e[i].val*siz[t]*(num-siz[t]) ;
	}
	head[x] = 0 ;
}

int main()
{
	scanf("%d" , &n ) ;
	int x , y ;
	for(int i = 1 ; i < n ; i ++ ) {
		scanf("%d%d" , &x , &y ) ;
		E[x].push_back( y ) ;
		E[y].push_back( x ) ;
	}
	dfs( 1 , 0 ) ;
	for(int i = 1 ; i <= n ; i ++ ) {
		scanf("%d" , &a[i] ) ;
		c[a[i]].push_back( i ) ;
	}
	for(int i = 1 ; i <= n ; i ++ ) {
		if( c[i].size() <= 1 ) continue ;
		col = i ; tot = 0 ;
		build( i ) ;
		calc( rt , 0 ) ;
	}
	printf("%lld\n" , ans ) ;
	return 0 ;
}

B

To

先考虑原树上 $dp$ ，好转移

放到虚树上，由于虚树上一条边代表了一段路径，我们钦定它断开时显然应该找原树这一段权值最小的一条边

预处理之

int dep[N] , fat[N][22] , Min[N][22] , dfn[N] , tim ;
void dfs( int x , int fa )
{
	dep[x] = dep[fa] + 1 , fat[x][0] = fa , dfn[x] = ++tim ;
	for(int i = 1 ; i <= 20 ; i ++ ) {
		fat[x][i] = fat[fat[x][i-1]][i-1] ;
		Min[x][i] = min( Min[x][i-1] , Min[fat[x][i-1]][i-1] ) ;// 预处理
	}
	for(int i = head[x] ; i ; i = E[i].lst ) {
		int t = E[i].to ;
		if( t == fa ) continue ;
		Min[t][0] = E[i].val ;
		dfs( t , x ) ;
	}
}
int LCA( int x , int y )
{
	if( dep[x] < dep[y] ) swap( x , y ) ;
	for(int i = 20 ; i >= 0 ; i -- ) {
		if( dep[fat[x][i]] >= dep[y] ) x = fat[x][i] ;
	}
	if( x == y ) return x ;
	for(int i = 20 ; i >= 0 ; i -- ) {
		if( fat[x][i] != fat[y][i] ) x = fat[x][i] , y = fat[y][i] ;
	}
	return fat[x][0] ;
}

int b[N] , p[2*N] , K , len , rt ;
bool is[N] ;
bool cmp ( int x , int y )
{
	return dfn[x] < dfn[y] ;
}
int Get( int x , int y )
{
	int res = 1e9 ;
	for(int i = 20 ; i >= 0 ; i -- ) {
		if( dep[fat[x][i]] >= dep[y] ) {
			res = min( res , Min[x][i] ) ;
			x = fat[x][i] ;
		}
	}
	return res ;
}
void build()
{
	sort( b+1 , b+K+1 , cmp ) ;
	len = 0 ; 
	p[++len] = 1 , p[++len] = b[1] ;
	for(int i = 2 ; i <= K ; i ++ ) {
		p[++len] = b[i] ;
		p[++len] = LCA( b[i-1] , b[i] ) ; 
	}
	sort( p+1 , p+len+1 , cmp ) ;
	len = unique( p+1 , p+len+1 ) - (p+1) ;
	rt = p[1] ;
	for(int i = 2 ; i <= len ; i ++ ) {
		int x = p[i] , y = LCA( p[i-1] , p[i] ) ;
		add1( y , x , Get(x,y) ) ;
	}
}
LL f[N] ;
void calc( int x , int fa )
{
	if( is[x] ) f[x] = LL(1e17) ;
	else f[x] = 0 ;
	for(int i = Hd[x] ; i ; i = e[i].lst ) {
		int t = e[i].to , v = e[i].val ;
		if( t == fa ) continue ;
		calc( t , x ) ;
		f[x] += min( f[t] , 1LL*v ) ;
	}
	Hd[x] = 0 ;
}
// each query
	scanf("%d" , &K ) ;
	for(int j = 1 ; j <= K ; j ++ ) scanf("%d" , &b[j] ) , is[b[j]] = 1 ;
	tot1 = 0 ;
	build() ;
	calc( rt , 0 ) ;
	if( f[rt] >= LL(1e17) ) {
		printf("-1\n") ;
	}
	else printf("%lld\n" , f[rt] ) ;
	for(int j = 1 ; j <= K ; j ++ ) is[b[j]] = 0 ;

C

To 充分利用虚树性质

这道题可以告诉我们：虚树本身是有非常多的性质的！

考虑建出了包含关键点的虚树之后，讨论一下所有点到最近关键点的情况：

对于被 “剪掉的树枝” （蓝色部分）：显然需要先走到被虚树包含 (被压缩的 或 本身就是虚树上节点) 的点上，

对于被 压缩的节点 (如 $5$ 号点) ：一定与所在虚树边的两端点中的一个情况相同，可以从深度较大的往上二分得到分界点

剩下虚树上的点，我们显然可以直接跑多源最短路，把所有关键点放堆里跑一次

然后就是一些 简单(烦人)分讨啦

D

To

题如其名，十分毒瘤，码量较大

E

To

一道不太一样的 “虚树” 题

发现本题实际上是要 动态维护虚树  ( LCT ？ 不会

有一个下位替代：用 $set$ 来维护

具体来说：$set$ 中只存关键点，按 $dfn$ 序排序

首先一个经典结论：树上若干个点的 $LCA$ 等价于 $dfn$ 序 最小和最大的两点的 $LCA$

这样我们就可以实时找到这个连通块的根了，再利用 $dfs$ 序的性质能够实现部分操作

对于本题，还有一个结论

DFS 序求出后，假设关键点按照 DFS 序排序后是 $a_1,a_2,...,a_k$
那么所有关键点形成的极小连通子树的边权和的两倍等于 $dis(a_1,a_2)+dis(a_2,a_3)+...+dis(a_k,a_1)$

如果是点权，那么要取 相邻两点路径上除它们 $LCA$ 以外的点权和，这样求和结果是 除整个连通块的 $LCA$ 外，所有点点权的 $2$ 倍

画图理解

那么本题维护一下插入删除时的贡献变化就做完了

最后再总结一下虚树注意事项：

1. 用两次 $sort$ 建虚树时要注意去重前的点数是 $2n$ 的，数组要开够

dfs tree

顾名思义，在 有向/无向图 中从某个点开始，按 $DFS$ 的顺序遍历，每个点只经过一次，形成的一棵树

处理图上问题有很大作用，如 $Tarjan$ 算法实际上就是基于 $dfstree$ 的