ubercool's blog

Doubt!!
By ubercool, history, 5 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use binary lifting to answer queries of the second type.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't they be answered without binary lifting??

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can reduce these queries to "what is the k-th ancestor of vertex v?" queries, which can be answered offline.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can I do that ??

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I understood that part but how you are storing the kth ancestors ??

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +11 Vote: I do not like it 
              std::vector<int> g[MAXN]; /* tree */
int a[MAXN]; /* DFS stack */
int t = 0;
std::vector<int> 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--;
}
              → Reply