DS on trees
Data structure/Divide and Conquer Technique On Trees
Centroid Decomposition（点分治）
DSU on Tree
Centroid Tree（点分树/动态点分治）
The essence of Centroid Decomposition:
Tanuj Khattar's Tutorial on Centroid Tree
Consider any two arbitrary vertices A and B and the path between them (in the original tree) can be broken down into A–>C and C–>B where C is LCA of A and B in the centroid tree.
The vertex C can also be seen as : If we assign labels to centroids in the order in which they are removed from the graph / labels equal to the level at which the centroid occurs in the centroid tree, then C would be the node with smallest label on the path from A–>B in the original tree
Therefore centroid tree breakdown every \(O(n^2)\) path by centroids in a certain layer. When we try to extract all paths passing by an arbitrary node \(u\), all relevant centroids are ancestors of \(u\) on centroid tree.
Additionally, non simple paths(which fall back to the same sub-tree as \(u\) on centroid tree) needs to be excluded.
Exercises:
Problem - G - Codeforces CF757G centroid tree + dynamic segment tree / Persistent Centroid Tree
Heavy-Light Decomposition （链分治）
Tricks
链加，单点查询\(\rightarrow\) 树上差分BIT
Exercises:
[SCOI2015]情报传递 - 洛谷 利用树上差分，维护一个点到根的和，单点修改时只用修改受影响的子树。
[LNOI2014]LCA - 洛谷 对于区间可减贡献，可以将\([l, r] \rightarrow[0, r] - [0, l - 1]\) 扫描线完成
[Ynoi2017] 由乃的 OJ - 洛谷 directed path, double constant. Difficulty: lxl