algorithm - Find vertex at distance d -

i have tree n vertices. want design algorithm answer queries. given vertex v , integer d, want find vertex @ distance d v. if there more 1 vertex @ distance d output any. know how brute-force. tried idea similar lca finding algorithm (calculating ancestors @ distance 1, 2, 4, 8...), without result.

i have many queries, 10^6, answer them in o(1) or o(log n) time

this approach work

1. compute centroid of longest path in tree. that, use depth-first search find vertex x max of vertex depths in tree rooted @ x minimal
2. compute depth of vertices in tree rooted @ x using simple tree traversal
3. group queries index of connected component query fall if x removed
4. iterate on queries component. query (v, d). if depth(v) <= d, can use d-th ancestor of v answer, using standard approach in o(log n). otherwise, check if there solution vertex w path(v, w) crossing x , dist(v, w) = d looking depth d - depth(v) in 1 of other components (e.g. in o(1) via hashing)

this works because if there answer query (v, d) depth(v) >= d, there path of length d starting @ v crosses x, due property of x.

you can implement steps 1 , 2 using single depth-first search.

for step 4, want keep hash table associates depth vertices in way can remove , add vertices in o(1). can perform in linear time when working component component.

the total run time o((n + q) * log n).

this can made online precomputing depth data structure step 4 using persistent binary search trees, again in o(log n) per query.