Hi everybody!
I was solving some ACM regional problems from Live Archive and I got stuck realy bad with this task:
There is a family of dragons represented as a rooted tree. Every dragon has a hatchyear and a deathyear, and they can have children. So, the task is to find for every dragon the deepest descendant that lives during its lifetime (between its hatchyear and deathyear).
I tried some things without any success, always receiving TLE or WA verdict.
However, I made a naive solution with dfs over all the dragons, looking for the deepest descendant and much to my surprise it was accepted O.o . The maximum amount of dragons can be as large as 50000, so in the worst case I'm pretty sure that N dfs shouldn't work (but it did)
Although I could "solve" this task, I really want to know if there is a solution that actually makes sense with such constraints. I thought about some queries with segment trees or some interval data structure, but nothing really useful came to my mind :(
Thanks!
I code that problem a few months ago, and Im pretty sure that O(n^2) shouldn't pass as you said. I was looking at my code and it is just a simple SegmentTree+Dfs problem. Total Complexity O(nlogn)
I knew it! hahaha I knew it had something to do with segment trees!
Can you give me a hint? I was trying using RMQ (maximum) to find the deepest descendant of a dragon, updating the intervals with the depth of the dfs. The answer for a dragon should be the maximum found in its lifetime (using hashing because hatchyear and deathyear can be as large as 10^9) but this won't work because it will find dragons that are not its descendants :-(.
Thanks!