Bungmint's blog

By Bungmint, history, 2 months ago, In English

I was trying to solve this problem using centroid decomposition, so first I created the centroid tree that also calculates the weighted distance between nodes, and then for the queries, I came up with an idea, akin to lazy propagation, where for each node, I store the query values (distance, color and when the query was made), then when I have to update a node, I push down the previous query values of the node to its children, and then update the node itself. Overall, when I have to update the color, I would do this process to all the ancestors of the node and the node itself. For the query queries, I answer it via checking all the ancestors and see which of the query value store in the ancestor can actually reach the queried node and out of which has the latest query time would be the answer. I was certain that this should probably work, but after getting WA about 10 times, I wonder if this approach is even correct or if the WA is due to some mistakes I made in my implementation. Any help would be appreciated.

Code(Only the important parts)
 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Your code fails for

6
4 1 34
2 6 80
2 3 35
5 6 31
3 4 77
3
1 4 197 8
1 1 128 2
2 2
ans = 8

And actually at your level I would expect you to know what stress-testing is, it's really useful

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the countertest. This will sound dumb, but I always hated to do stress-testing because I am lazy and also writing a generator, bruteforce solution, and a checker for a problem that you probably used the wrong approach seems like a lot of effort and time, when you can spend that time just attempting a different approach to the problem, but I agree that doing stress-testing is definitely better than me struggling on a question for hours when I could have figured out what the issue was.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +51 Vote: I do not like it

      Being lazy is one thing. But asking others for help instead of stress-testing? Not cool.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Hi Errichto, I am a big fan of your youtube channel. The main reason I asked for help is because I was completely stuck and could not figure out any other approaches to solve the problem, so even if I did all the stress-testing and found out that my solution is flawed, I don't think I would have found an alternative way to solve the problem, but still if you think this was unnecessary, I will refrain myself from asking frequently.

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I just got AC with approach similar to what you described.

Not sure what are you doing exactly (didn't read your code), but I have no propagation, each query (no matter which type) to some vertex $$$v$$$ visits exactly all its parents in the centroid tree. Maybe it is the difference. In each vertex I maintain a structure that solves a problem like if it was a root of a bamboo tree (actually, it is a simple vector only), when I need to process a query of the first type with parameters $$$v, d, c$$$, I visit all centroid parents $$$p$$$ of the vertex $$$v$$$ and place there a query with the distance $$$d - dist(p, v)$$$. When I need to answer the query of the second type, I just visit same parents $$$p$$$, ask a query with the distance $$$dist(p, v)$$$ and choose the answer with the most recent timestamp.

The proof why it works is more or less straightforward, I am sure that you can do it yourself.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much! The propagation bit was just me not being able to come up with a data structure that can store the information needed. Using your approach, I was able to AC the problem. For anyone struggling with this problem, here is my code (uploaded on pastebin) Link