dx24816's blog

USACO newbarn
By dx24816, history, 6 years ago, In English

Hello,

Can someone explain the solution to USACO newbarn (Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=817, Solution: http://www.usaco.org/current/data/sol_newbarn_platinum_feb18.html)? I don't understand what his variables names mean, like tree[c].top, tid, etc. Can someone explain what all of his variables mean and how each part of his program works, including his centroid decomposition? Thanks!

Edit: OK, if anyone has a centroid decomposition solution that's not the official solution (I can't understand how the checking for the same subtree idea works), can you post it and explain it in depth? Also, when you're talking about trees and childs, can you distinguish between children on the actual tree or the centroid tree?

-dx24816

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by dx24816 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by dx24816 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by dx24816 (previous revision, new revision, compare).

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

For this problem, there is a much easier solution. You just have to store the two endpoints of the diameter. Whenever you query a point, the longest path has to be between the point and one of the two endpoints.

If the longest path is not between the point and one of the endpoints, then that means there is a longer path than the diameter, which is clearly untrue. (Let's take our current node to have a distance to the diameter's path of x, distance to the farthest node independent of the diameter's path as y, and the diameter's lengths to be a and b (split by the node that connects to the current node). Then a + b >= b + x + y, and a + b >= a + x + y, so a >= x + y, and b >= x + y. The three lengths we could consider are a + x, b + x, y, and obviously y is lesser than the two of these, so we just have to check the endpoints).

I intended for the problem's solution to be square root decomposition. I can give you the code and explanation for the sqrt decomp, if you like.

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

    It would be great if you share and explain your solution, since I also need to learn more about sqrt decomposition. However, I would also like to see and understand a working centroid decomposition solution because I did this problem with the hope that this would help me better understand centroid decomposition. I solved the Xenia and Tree problem, and this seemed like an easy extension (instead of minimum distance, you want maximum), but I couldn't figure it out.

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

      I didn't write a centroid decomp. What "checking for the same subtree idea" means is that you just don't care about it if the longest path doesn't pass through the centroid — because once you decompose it, you'll check the non-current-centroid paths somewhere in the next couple decompositions.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        I was going to send you the file. But for some reason between yesterday and now my entire C++ folder got wiped clean of files. All my codes are gone. I'm pretty sure I have a virus, lol.

        UPD: I couldn't recover any of the files. Apparently norton power eraser deleted everything in the folder because it thought my compiled code was a virus. GG boys, bye bye 1 year of code. (On the bright side, I can get it all back from online judges.)

        UPD2: pulled it off usaco

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

      Here's the sqrt decomp one, with explanation included. https://hastebin.com/sepemumema.cpp

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

Anson, didn't you create this problem? XD

→ Reply