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 ??

• 0

 » 11 months ago, # |   0 You can use binary lifting to answer queries of the second type.
•  » » 11 months ago, # ^ |   0 Can't they be answered without binary lifting??
•  » » » 11 months ago, # ^ |   0 You can reduce these queries to "what is the k-th ancestor of vertex v?" queries, which can be answered offline.
•  » » » » 11 months ago, # ^ |   0 How can I do that ??
•  » » » » » 11 months ago, # ^ |   0 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.
•  » » » » » » 11 months ago, # ^ |   0 I understood that part but how you are storing the kth ancestors ??
•  » » » » » » » 11 months ago, # ^ |   +11 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--; } 
•  » » » » » » » » 11 months ago, # ^ |   -8 Isn't that binary lifting
•  » » » » » » » » » 11 months ago, # ^ |   0 No
•  » » » » » » » » » 11 months ago, # ^ |   0 Thanks!!