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

How to solve Hotels from POI?
Автор vatsal, история, 7 лет назад, По-английски

How to solve this problem from POI? It simply states: Given a tree find a triplet of nodes (a,b,c) such that distance between each other is same!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

That's not what the problem is asking. It asks to compute the number of such triplets.

You can prove that for any such triplet, there must exist another vertex L which is between them in the tree (i.e., L-A, L-B, L-C forms a star-like shape), and the distances L-A, L-B, L-C must be equal. So you loop over every vertex L, then run DFS counting vertices at each distance. Gives O(n^2) runtime.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Won't that overcount? Like in the sample itself, the distance of nodes {4, 6, 7} are all 2 from the node 2, so we count them once, but then the nodes {4, 6, 7} are also at distance 1 from the node 5 and so we count them again. How do we account for this?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      Right. You should only count triples which are in different branches of the tree going out of L. (Note that there may be Ω(n) of these branches, so you need to do that in a non-slow way.)

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Check out this

→ Ответить