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

虚树

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

适用于优化某些在整棵树上进行 $d p$ 、 $df s$ 的问题

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

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

Warning

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

在这里插入图片描述

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

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

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

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

思想懂了，来看具体实现

build 建树

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

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

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] ;
}

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

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

例题

A

To 在这里插入图片描述
直接在原树上跑 $n$ 次 $df s$ 显然会超时

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

#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

在这里插入图片描述
先考虑原树上 $d p$ ，好转移

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

预处理之

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 ;