### dvdg6566's blog

By dvdg6566, 14 months ago,

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!

• +350

 » 14 months ago, # |   +55 It would be great if you add the resources to learn about them.
•  » » 14 months ago, # ^ |   +61 Hmm I could compile that in the future if people would find that helpful
•  » » » 14 months ago, # ^ |   +19 Add virtual trees, they’re cool :D
•  » » 14 months ago, # ^ |   +43 also it would be helpful if someone enlist some good educational problems on above topics.
 » 14 months ago, # |   +38 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 ?
•  » » 14 months ago, # ^ |   +13 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.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +11 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.
 » 14 months ago, # |   -6 Nice, if you can add some questions to it.
 » 14 months ago, # |   +10 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.
•  » » 14 months ago, # ^ |   0 Could I check if reachability tree means link-cut?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +10 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.
•  » » » » 14 months ago, # ^ |   0 Yeah, I think it refers to the same idea
 » 14 months ago, # |   +18 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"?
•  » » 14 months ago, # ^ | ← Rev. 3 →   +8 Is the one where u do knapsack-like dp on tree
•  » » 14 months ago, # ^ |   +8