原理:将树以一种划分方式分成若干条链,转换为区间,再用数据结构维护
一般形式:两遍dfs初始化+数据结构(线段树/树状数组)
解决的问题:各种树上区间操作(维护的东西越多,解决问题的范围就越大)
两遍dfs维护的:
$fa$[ ](父节点)
$son$[ ](重儿子)
$dep$[ ](深度)
$siz$[ ](子树大小)
$seg$[ ](树中点在数据结构(如线段树)中编号)
$rev$[ ](数据结构中点在树中编号)
$top$[ ](重链头)
轻重边的一些性质:
1.如果(u, v)为轻边,则size[v] <= size[u] / 2。
2.从根到某一点v的路径上,轻边个数不多于O(logn)。
3.称某条路径为重路径(重链),当且仅当它全部由重边组成,一个点也算一条重路径。那么对于每个点到根的路径上都有不超过O(logn)条轻边和O(logn)条重路径。
4.每个点都在且仅在一条重路径上,每条路径一定是一条从根结点方向向叶结点延申的深度递增的路径。
标签:两遍,剖分,线段,dfs,树链,数据结构
From: https://www.cnblogs.com/hirasawayuii/p/18677473