Graphs -> Trees¶

Tree structure, rooting, Euler tours, diameters, and decomposition ideas that power most advanced tree problems.

Microtopics¶

Source	Type
IOI 2025 syllabus PDF	`Primary`
OI Wiki tree basics	`Reference`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Diameter of a Tree	`AOJ`	`Easy`	-	-	-	Tree Diameter; DFS; Weighted Tree	Very clean tree baseline problem.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Finding a Centroid	`CSES`	`Medium`	Subtree Sizes, Centroid	Size DFS; Balance Check; Candidate Descent	DFS; Tree Balance	Balance; DFS	A compact tree problem that reinforces subtree-size reasoning.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Distinct Colors	`CSES`	`Hard`	DSU On Tree, Subtrees	Small-To-Large Merging; Subtree Frequency Maps; Offline Aggregation	Tree Traversal; Frequency Maps; Subtree Processing	Distinct Values; Subtree Aggregation; Small-To-Large	A strong subtree-aggregation problem that rewards a nontrivial tree technique.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Subtree Queries	`CSES`	`Medium`	Euler Tour, Fenwick	Flatten Tree; Fenwick Tree; Range Sum Queries	Fenwick Tree; Subtree Intervals	Subtree Sum; Updates	A canonical tree-to-array reduction for subtree updates and queries.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Distances I	`CSES`	`Medium`	Rerooting, Distances	Two-Pass DP; Downward And Upward Values; Distance Maxima	Tree DP; DFS; Rerooting Idea	Eccentricity; Distance Propagation; Tree DP	Per-node farthest-distance computation on a tree.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Distances II	`CSES`	`Medium`	Rerooting, Sums	Subtree DP; Reroot Transition; Sum Aggregation	Tree DP; Prefix Sums On Trees	Sum Of Distances; Tree DP	A classic rerooting problem where each node needs an aggregate over the whole tree.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Path Queries	`CSES`	`Medium`	Euler Tour, Fenwick	Euler Tour; Fenwick Tree; Prefix-On-Tree	Tree Flattening; Fenwick Tree; Rooted Tree	Root Path Sum; Updates; Tree Flattening	Pairs a tree traversal with range data structures in a very reusable way.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Subordinates	`CSES`	`Easy`	DFS, Subtree Sizes	Postorder DFS; Size Accumulation; Rooted Traversal	Tree Traversal; Parent-Child Relation	Subtree Size; Rooted Tree; Counting	A very approachable rooted-tree problem that builds subtree intuition.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Diameter	`CSES`	`Easy`	DFS, Diameter	Double Sweep; DFS/BFS Diameter; Farthest Node	Tree Basics; Graph Traversal; Distance Intuition	Two BFS; Longest Path	The classic tree diameter pattern that every tree toolkit should contain.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Tree Matching	`CSES`	`Medium`	Tree DP, Greedy	Bottom-Up DP; Leaf Processing; Pairing Choices	DFS; Greedy Reasoning	Matching; Independent Edges; Independent Edge Set	A concise introduction to optimizing choices on trees.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`CIELTHECOMMANDER`	Ciel the Commander	`secondary`	`hard`	centroid decomposition; centroid tree labeling; balanced recursive split	Note	Code
`COMPANYQUERIES2`	Company Queries II	`secondary`	`medium`	binary lifting; depth equalization; lowest common ancestor	Note	Code
`KINGDOMS`	KINGDOMS	`secondary`	`hard`	laminar regions; sweep events; containment tree	Note	Code
`MCQUERY`	MinCut Query	`secondary`	`hard`	all-pairs min-cut; cut tree; count pairs by threshold	Note	Code
`MTREECOL`	Color a tree	`primary`	`hard`	ratio greedy; tree contraction; exchange argument	Note	Code
`PATHQUERIES2`	Path Queries II	`secondary`	`medium`	heavy light decomposition; path query decomposition; segment tree on base array	Note	Code
`SUBTREEQUERIES`	Subtree Queries	`secondary`	`medium`	euler tour flattening; subtree interval; fenwick point set range sum	Note	Code
`TREEMATCHING`	Tree Matching	`secondary`	`medium`	tree matching dp; matched or unmatched state; child swap contribution	Note	Code
`VMWTREE`	Lại là cây khung	`primary`	`hard`	path reverse; path sequence queries; heavy-light decomposition	Note	Code
`VOITSORT`	Cây hoán vị	`secondary`	`hard`	lexicographic enumeration; stack-sortability; cartesian tree view	Note	Code
`VOSTRIP`	VOSTRIP	`secondary`	`hard`	tree endpoint pairing; path decomposition; local imbalance formula	Note	Code

python3 scripts/generate_problem_catalog.py