Dsu On Tree 总结

Dsu On Tree 总结

 
树上启发式合并，处理树上 子树统计 且 离线 问题

与点分治不同，大多数情况 dsu on tree 处理的都是有根树

借助重链剖分的原理，复杂度很优秀

通常的步骤：

一、 将询问离线，挂在节点上

二、 第一次 dfs 预处理出所有重儿子

三、 第二次 dfs 统计答案：

1. dfs 当前点的所有轻儿子，处理轻子树中的节点，每处理完一个轻子树，回退其在维护答案的数据结构中的影响

2. 处理完轻子树后， dfs 当前点的重儿子，将维护重儿子子树 全部 信息的 vec 与 当前节点 swap

3. 再 for 一遍所有轻子树的 vec ，加入 维护答案的数据结构 以及 当前点的 vec 中，同时统计答案

4. 依据 当前点 是其 父亲的重/轻儿子，决定是否回退：回退时需要回退所有，也包括当前重儿子。直接枚举当前点的 vec 即可

与常规的 dsu 类似，树上 dsu 的复杂度 主要体现在枚举 vec 中元素上

那么我们考虑每个点对复杂度的影响 —— 显然只有当其某个祖先往父亲连了一条轻边时才会被枚举

而每个点到根的路径上的轻边数是 l o g log log 级的，那么复杂度通常为 O ( n l o g M ) O(nlogM) O(nlogM)， M M M 为所维护数据结构的复杂度

虽然说 启发式 通常是要用到 vec 的，但树的特点使得我们可以使用一种更为简洁的写法

例 1

不妨在第一次 pre_dfs 时处理出 整棵树的 dfn 序，将轻子树往上合并时直接枚举 dfn ，更新 存储答案的 数据结构

直接上板子：

#include<bits/stdc++.h>
using namespace std ;typedef pair<int,int> PII ;
typedef long long LL ;
const int N = 1e6 + 100 ;int n ;
vector<int> E[N] ;int siz[N] , mx[N] , L[N] , R[N] , nam[N] , tim , dep[N] ;
void pre_dfs( int now , int fa )
{siz[now] = 1 ;L[now] = ++tim , nam[tim] = now ; dep[now] = dep[fa] + 1 ; for(auto t : E[now] ) {if( t == fa ) continue ;pre_dfs( t , now ) ;siz[now] += siz[t] ;if( siz[t] > siz[mx[now]] ) mx[now] = t ;}R[now] = tim ;
}
int cnt[N] , id , Min , Ans[N] ;
inline void ins( int x , int f ) // 将 x 节点插入维护答案的 数据结构 
{cnt[dep[x]] += f ;if( cnt[dep[x]] > Min ) {Min = cnt[dep[x]] ;id = dep[x] ;}else if( cnt[dep[x]] == Min ) {id = min( id , dep[x] ) ;}
}
void dfs( int now , int fa , bool M )
{for(auto t : E[now] ) {if( t == fa || t == mx[now] ) continue ;dfs( t , now , 0 ) ;} // 先轻，清if( mx[now] ) {dfs( mx[now] , now , 1 ) ;}// 后重，不清ins(now,1) ;for(auto t : E[now] ) {if( t == fa || t == mx[now] ) continue ;for(int i = L[t] ; i <= R[t] ; i ++ ) { // 直接枚举 dfn int X = nam[i] ;ins(X,1) ;}}Ans[now] = id - dep[now] ; // 处理询问if( !M ) { // 清for(int i = L[now] ; i <= R[now] ; i ++ ) {int X = nam[i] ;ins(X,-1) ;}id = 1e9 , Min = 0 ;}
}int main()
{   scanf("%d" , &n ) ;int x , y ;for(int i = 1 ; i < n ; i ++ ) {scanf("%d%d" , &x , &y ) ;E[x].emplace_back( y ) ;E[y].emplace_back( x ) ;}pre_dfs( 1 , 0 ) ;id = 1e9 , Min = 0 ;dfs( 1 , 0 , 1 ) ;for(int i = 1 ; i <= n ; i ++ ) {printf("%dn" , Ans[i] ) ;}return 0 ;
}

例2

有些复杂，看上去像点分治，但本题处理的是 子树询问 ，点分治的分治中心无法维护原树的 root 信息

考虑 dsu

重新排序后回文串，可以看成 出现次数为 奇数 的字符 小于等于 1 1 1 个

最终的合法情况是 ( 00..0 ) 2 , ( 10..0 ) 2 , ( 01..0 ) 2 , . . . , ( 00..1 ) 2 (00..0)_2,(10..0)_2,(01..0)_2,...,(00..1)_2 (00..0)2​,(10..0)2​,(01..0)2​,...,(00..1)2​

字符只有 22 个，加上奇偶想到压状态， c n t [ s ] cnt[s] cnt[s] 表示当前匹配状态为 s s s ，最大长度

对于一个状态，显然只需保留最大的长度即可，那么这样的状态是不会漏最优值的

借助点分治的思想，每枚举一个轻子树中的节点，考虑 能否在已处理的子树中找到一条与之匹配的一段路径

那么枚举最终合法情况，在 c n t cnt cnt 中查一个 X O R XOR XOR 值就 OK 啦

(qwq…这还是之前 vec 合并版的码风)

#include<bits/stdc++.h>
using namespace std ;
#define mk make_pair
#define s first 
#define len second typedef pair<int,int> PII ;
typedef long long LL ;
const int N = 5e5 + 100 , T = 25 ;int n ;
struct nn
{int lst , to ;
}E[N] ;
int head[N] , tot ;
inline void add( int x , int y )
{E[++tot] = (nn){ head[x] , y } ;head[x] = tot ;
}int siz[N] , mx[N] , a[N] , dep[N] ;
void get_son( int now , int fa )
{siz[now] = 1 ; dep[now] = dep[fa] + 1 ;for(int i = head[now] ; i ; i = E[i].lst ) {int t = E[i].to ;if( t == fa ) continue ;a[t] ^= a[now] ;get_son( t , now ) ;siz[now] += siz[t] ;if( siz[t] > siz[mx[now]] ) mx[now] = t ;}
}
int cnt[1<<T] , ans[N] , Rs[24] ;
vector<PII> ve[N] ;
void dfs( int now , int fa , bool M )
{int res = 0 ;for(int i = head[now] ; i ; i = E[i].lst ) {int t = E[i].to ;if( t == fa || t == mx[now] ) continue ;dfs( t , now , 0 ) ;res = max( res , ans[t] ) ;// 因为是子树内部，所以还需要一个小小的树形DP}if( mx[now] ) {dfs( mx[now] , now , 1 ) ;res = max( res , ans[mx[now]] ) ;swap( ve[now] , ve[mx[now]] ) ;}ans[now] = -1 ;// ins now for(int i = 0 ; i < 23 ; i ++ ) {if( cnt[a[now]^Rs[i]] != -1 ) {ans[now] = max( ans[now] , dep[now]+cnt[a[now]^Rs[i]] ) ;}}ve[now].push_back(mk(a[now],dep[now])) ;if( cnt[a[now]] < dep[now] ) {cnt[a[now]] = dep[now] ;}// ins light_sonfor(int i = head[now] ; i ; i = E[i].lst ) {int t = E[i].to ;if( t == fa || t == mx[now] ) continue ;for(auto X : ve[t] ) { // 仿照点分治，先计算，再更新 for(int i = 0 ; i < 23 ; i ++ ) {if( cnt[X.s^Rs[i]] != -1 ) {ans[now] = max( ans[now] , X.len+cnt[X.s^Rs[i]] ) ;}}}for(auto X : ve[t] ) {ve[now].push_back( X ) ;if( cnt[X.s] < X.len ) {cnt[X.s] = X.len ;}}vector<PII> tt ;swap( tt , ve[t] ) ;// 清空，节省空间}if( ans[now] != -1 ) ans[now] = max( res , ans[now] - 2*dep[now] ) ;if( !M ) { // 回退 for(auto X : ve[now] ) {cnt[X.s] = -1 ;}}
}
int main()
{   scanf("%d" , &n ) ;int r ; char c ;for(int i = 2 ; i <= n ; i ++ ) {scanf("%d %c" , &r , &c ) ;add( r , i ) ;a[i] = 1<<(c-'a') ;}dep[0] = -1 ;get_son( 1 , 0 ) ;memset( cnt , -1 , sizeof cnt ) ;memset( ans , -1 , sizeof ans ) ;for(int i = 1 ; i < 23 ; i ++ ) Rs[i] = (1<<(i-1)) ;dfs( 1 , 0 , 1 ) ;for(int i = 1 ; i <= n ; i ++ ) {printf("%d " , ans[i]==-1?0:ans[i] ) ;}return 0 ;
}

 
 
另外几道题：

基础板子，也可以线段树合并

板子，结合 map —— O(log)型 的数据结构

统计出现次数的技巧，集合只增不减可以将 “=” 转化为 “>=”

通过 dsu 来维护 贪心 / DP 的策略

有些复杂的转化，维护连续段的技巧很妙

待补

从以上的描述，我们可以总结出一些经验：

1. Dsu 处理的是 离线 且 子树询问 的问题
2. 通常是点权，而且要使得 维护答案的数据结构在从 儿子 继承给 父亲 时不需要做出改变，即：点权是全局的点权，而非当前子树内部的
3. 本质是一个优雅的暴力，拓展性极强，可以结合许许多多的 技巧 和 数据结构
4. 不用考虑维护的信息是否 可撤销（如Max），表面上看到的 对轻子树的 撤销 实际上是一个 维护答案数据结构的全局清空操作，那么自然不用考虑维护历史版本
5. 与 树上线段树合并 相比，可以维护更多的 “坐标” ，或者说是 “限制”（二维甚至更多），潜能在于那个 维护答案的数据结构