ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1752. Tree 2

Good problem!
Posted by Felix_Mate 28 Dec 2015 19:10
I got AC with O(N*sqrt(N)),but my solution is very hard(274 lines and many different subtasks). Who can say simple solution(idea without code)?
Re: Good problem!
Posted by Umaru Doma 5 Jul 2016 13:08
Hi. This is my solution for this problem.
Let's find two farthest nodes in tree. Let's call it f1 and f2. It can be done by two bfs'. Now let's answer for queries. Let the y farthest node from x(it's f1 or f2). If such node exists that dist(x, z) = d, then it would lie on path from x to y. If dist(x, y) < d, answer would be 0. Let l be lca(x, y). If dist(l, x) <= d, answer would be dist(l, x)'th parent of x. If x is ancestor of y, answer would be (dist(x, y) - d)'th parent of y. Otherwise answer would be dist(l, y) - (d - dist(l, x)).
Sorry for my poor English.
Re: Good problem!
Posted by ASK 28 Feb 2018 14:52
O(N*log(N)), ~100 lines of code, ~1K gzipped

For every edge out of a node we calculate L, the length of the longest path from this node thru the edge. It is two DFS: the first one to calculate L for downward edges, the second one to fix the upward edges.

At most two edges (with the largest L) of each node are needed to calculate the longest paths (the second is needed for the situations where we get from node A into node B and in node B the edge B->A has the maximal L). For these two edges we precalculate short-cuts: for all i, such that 2^i ≤ L, we save the node C that can be reached after 2^i steps and from which edge in C it was reached.
Re: Good problem!
Posted by scidylanpno 6 May 2019 16:09
My solution is quite simple, just find one farthest nodes pair in the tree by two DFSs, denoting f1 and f2. Then use f1 as root and dfs to calculate the 2^i steps' father of every node x. And use f2 as root similarly. Then the answer can be done by express d to the binary form and jump at most log(n) to find an answer under these two roots.