Part VI · Graph Algorithms and Tree-Graph Techniques
42. Advanced Tree Algorithms on Graphs
11 lessons•46 topics•Intermediate / Advanced
0 of 11 lessons published
42.01Outline
LCA fundamentals
- Naive parent climbing
- Depth alignment
- Binary lifting
- Euler tour + RMQ
42.02Outline
Tree distances and paths
- Root distances
- Distance(u,v)
- Path reconstruction
- Path sums
- Weighted edges
42.03Outline
Euler tours
- Entry/exit times
- Subtree as interval
- Euler array
- DFS ordering
- Flat-tree representation
42.04Outline
Binary lifting extensions
- Kth ancestor
- Kth node on path
- Min/max edge on path
- Function composition jumps
42.05Outline
Tree DP
- Subtree size
- Tree diameter
- Independent set
- Maximum matching on tree
- Weighted distances
42.06Outline
Rerooting DP
- All-root distance sums
- Rerooting transitions
- Prefix/suffix contribution combination
42.07Outline
Heavy-light decomposition
- Heavy child
- Chain heads
- Path decomposition
- Segment tree integration
- Path updates/queries
42.08Outline
Centroid decomposition
- Centroid selection
- Recursively split tree
- Distance-to-centroid lists
- Path queries
42.09Outline
DSU on tree
- Small-to-large merging
- Sack technique
- Distinct colors in subtree
- Frequency maintenance
42.10Outline
Virtual trees
- Relevant-node compression
- LCA closure
- Stack construction
- Queries on selected nodes
42.11Outline
Tree isomorphism intro
- Rooted tree canonical forms
- AHU hashing idea
- Unrooted center reduction