ubercool's blog

By ubercool, history, 11 months ago, , I am solving the problem QTREE2 on Spoj.[](http://www.spoj.com/problems/QTREE2/) I am learning LCA and I have calculated LCA using euler tour.But I am unable to find the answer to the second type of query which asks about Kth node in a path from node a to node b in a tree.How do we solve it ?? Comments (10)
 » You can use binary lifting to answer queries of the second type.
•  » » Can't they be answered without binary lifting??
•  » » » You can reduce these queries to "what is the k-th ancestor of vertex v?" queries, which can be answered offline.
•  » » » » How can I do that ??
•  » » » » » We can split the (a, b) path in two segments, , and . If |p1| ≤ k, the answer is the (|p1| - 1)-th ancestor of vertex a. Otherwise, it is the (|p1| + |p2| - 2 - k)-th ancestor of vertex b.
•  » » » » » » I understood that part but how you are storing the kth ancestors ??
•  » » » » » » » std::vector g[MAXN]; /* tree */ int a[MAXN]; /* DFS stack */ int t = 0; std::vector q[MAXN]; void query(int k, int v) { q[v].push_back(k); } int dfs(int v = 0, int p = -1) { a[t++] = v; /* for all i in q[v], a[t - i] is the i-th ancestor of v */ for(int c: g[v]) if(c != p) dfs(c, v); t--; }
•  » » » » » » » » Isn't that binary lifting
•  » » » » » » » » » No
•  » » » » » » » » » Thanks!!