Блог пользователя dvdg6566

Автор dvdg6566, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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 ?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
      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.

»
4 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Nice, if you can add some questions to it.

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +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"?