You can dynamically update amount of branches per-type per-distance for each horizontal step leading to O(W*H*9)

Edited by author 09.06.2026 11:10

very vertical

It's O(N) problem with O(1) memory (apart from string itself)

BFS for shortest path, but not over original graph - over the chain itself. There are edges of weight 1 and 0.

what is "T"?
give please full description.

I think it's a test like:

3
0 0
0 3
0 2

and I just adjust my program

600 400 152 63 152
Solution exists.

sqrt(n) decomposition also works here (0.5 sec) and easier to implement
it's actually does not differ much because heavy-light with segment/fenvick over chains will be something like Q*log^2(N) with bad constant over it

{$m 100000000000000000000}

You can use "G++ 9.2 x64" language to avoid it

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.

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.

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.

We can actually solve it on just O(N) time.

Let's set vertex 1 as a root.

Now let's at first find the depths of subtree of each vertex, deepest vertex in each subtree and the distance from the root for each vertex. This can be done in one DFS.
Let's name them as:
1) depth[ver] -> depth of a subtree of vertex ver
2) dist[ver] -> distance from vertex 1 to vertex ver
3) mx_ver[ver] -> deepest vertex in a subtree of vertex ver

Now we can check for all queries:
1) If query is (v, d) and depth of vertex v is >= d, then the answer is the parent of vertex mx_ver[v] on distance (depth[v] - d) (so we should somehow later go up from vertex v to (depth[v] - d) edges). Let's store it in mx_ver[v].
2) If query is (v, d) and distance from root to v >= d (so dst[v] >= d), then the answer is the parent of vertex v on distance d, let's store this information in vertex v.

What should we do with all the other queries?
All other queries (v, d) tell us that the answer for them will look somehow like this:
Take vertex v, go up several edges, then go down to some other subtree.
So we need to take some ancestor of v and go into it to a subtree different from a subtree containing vertex v.
Let's say that this ancestor is some vertex u and the depth of its deepest subtree not containing v is H. Then if (dst[v] - dst[u] + H) >= d, we can choose u as a suitable ancestor. And the answer for the query will be the parent of the deepest vertex in subtree H on distance d - (dst[v] - dst[u] + H).
Great thing about these formulas is that if we stay in some vertex v during some DFS, for all our ancestors the number (H - dst[u]) is a constant and we can keep the maximum value of it on current path.

So what should we do next?
Let's simply run one more DFS. During our walk through the tree in the DFS let's keep maximum value of (H - dst[u]) for all our ancestors. To do this we need to do some routine stuff:
1) Calculate two maximums by depth[to] + 1 for all children (if we will go to the subtree with first maximum, we will use H - dst from the second one).
2) Before going into some child check if the new found values are larger then global maximum (H - dst[u]).
3) Not forget to carefully restore this global maximum going up on each step.
4) Each time we take new maximum for (H - dst[u]), also store the deepest vertex in the subtree H.
Then in each vertex during this DFS we also need to iterate through all remaining queries for this vertex and try to set an answer to them, again in form "Answer for this query is a parent of some deepest vertex in some subtree H on distance (dst[v] + (H - dst[u])) - d"

The final step would be to run one more DFS and in all vertices with stored info "go up to distance X" do this by simply storing current DFS path and writing needed parent as an answer for the corresponding query.

#pragma comment(linker, "/STACK:16777216")