Hi everybody!

I was solving some ACM regional problems from Live Archive and I got stuck realy bad with this task:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=519&page=show_problem&problem=4002

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!