虛樹

虛樹，顧名思義是 只關注原樹上的某些 關鍵點，在保留原樹祖孫關系的前提下建出的一棵邊數、點數大大減少的樹

適用于優化某些在整棵樹上進行 $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 queryscanf("%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$ 的