Блог пользователя ubercool

Doubt!!
Автор ubercool, история, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can't they be answered without binary lifting??

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        How can I do that ??

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 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.

          → Ответить
          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится 
              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--;
}
              → Ответить