ubercool's blog

By ubercool, history, 10 days 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 ??

 
 
 
 

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't they be answered without binary lifting??

    • »
      »
      »
      10 days 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.

      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How can I do that ??

        • »
          »
          »
          »
          »
          10 days 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.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              10 days 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--;
              }