dvdg6566's blog

A list of important concepts in Tree-based Problems
By dvdg6566, 4 years ago, In English

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!

  • Vote: I like it
  • +350
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

It would be great if you add the resources to learn about them.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    Hmm I could compile that in the future if people would find that helpful

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    also it would be helpful if someone enlist some good educational problems on above topics.

    → Reply
»
4 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Nice, if you can add some questions to it.

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could I check if reachability tree means link-cut?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I think it refers to the same idea

        → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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"?

→ Reply