Good problem! 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! 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! 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. |