Trees are a subset of graph theory problems that use the features of a tree:
- Acyclic
- Exactly 1 path between every pair of nodes.
Important algorithms (hopefull) exhaustive list:
- Preorder + Data strcutures
- Dynamic Programming on tree
- $$$2^K$$$ Decomposition of tree (and Lowest Common Ancestor)
- Kruskal Reconstruction Tree (KRT) (IOI Werewolf trick)
- Set Merging (with linear height merging)
- $$$O(N^2)$$$ Distribution DP
- "Re-rooting" tree DP (where you DP twice, once going down and once propagating from top)
- Centroid Decomposition
- Heavy-Light Decomposition
- UFDS on tree (See: CEOI 2017 Streets)
- (Edit: Thanks errorgorn ) Greedy for furthest node (See: RU Code Funny Salesman)
Would be interested to see if anyone has any suggestions what I missed out on!
It would be great if you add the resources to learn about them.
Hmm I could compile that in the future if people would find that helpful
Add virtual trees, they’re cool :D
also it would be helpful if someone enlist some good educational problems on above topics.
Could you provide some references / example problems for - Kruskal Reconstruction Tree - Distribution DP Also by Set Merging do you mean DSU or DSU on tree on those lines ?
Set merging on tree is like the problem IOI 2011 Race.
Alternatively, try this problem:
Given a tree of N nodes find the number of pairs exactly distance K apart in
O(N)time.How do you do this? I can't seem to figure it out.
Edit: It turns out this was already answered by a stackoverflow comment.
Nice, if you can add some questions to it.
There was a pretty interesting discussion on the line-tree (or the Kruskal tree) here. Is it the same as the Kruskal Reconstruction Tree? The same link also mentions auxiliary trees and reachability trees, so they might also be worth adding to the list.
Could I check if reachability tree means link-cut?
This tutorial might be helpful to disambiguate between the two. I think it uses the IOI Werewolf idea, so it might be similar to the Kruskal Reconstruction Tree, but I am not so sure.
Yeah, I think it refers to the same idea
Can you tell 1 example problem of the "Distribution DP" trick?
I am not able to figure out what it is from the name alone...
Is it another name for "Tree Convolution DP"?
Is the one where u do knapsack-like dp on tree
For example: https://dunjudge.me/analysis/problems/1812/ and https://atcoder.jp/contests/aising2019/tasks/aising2019_e
https://oj.uz/problem/view/COCI19_dzumbus