shsh's blog

What's the point of maintaining stack in virtual tree?
By shsh, history, 12 months ago, In English

In every virtual tree implementation I can find (https://en.oi-wiki.org/graph/virtual-tree/, https://mirror.codeforces.com/blog/entry/140066 , for instance), there seems to be an unnecessarily complex method to construct edges involving some kind of stack. The stack method used here is thankfully much simpler than both of these, but can't we simplify it even further to not use a stack at all?

That is, instead of:

for (int i = 1; i < (int)res.size(); i++) {
	while (tin[res[i]] > tout[stk.back()]) { stk.pop_back(); }

	vadj[stk.back()].push_back(res[i]);
	stk.push_back(res[i]);
}

(From the USACO Guide implementation)

We could just write:

for (int i = 1; i < (int)res.size(); i++) {
	vadj[lca(res[i - 1], res[i])].push_back(res[i]);
}

Is there any case in which this approach is wrong? I made this modification and still got accepted on the relevant AtCoder problem.

Edit: the usaco.guide module has since been updated, but I'm still not sure what advantage the second implementation on OI Wiki here has over the first one (which matches more closely with what I've described here), since both implementations seems to have O(n log n) runtime.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

shsh orz

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If you have the following complete binary tree with 7 nodes, indexed from top to bottom, left to right with 1..7, then if you want to build the virtual tree of the leaves, i.e. 4..7, you should get the entire tree, but with the bottom implementation, when you do lca(5, 6) = 1, you will add an edge from 1 to 6 which does not make it a tree anymore I think.

→ Reply
  • »
    »
    12 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    However res is computed like so:

    vector<int> res = key;
sort(res.begin(), res.end(), sort_tin);

for (int i = 1; i < (int)key.size(); i++) {
	res.push_back(lca(key[i - 1], key[i]));
}

sort(res.begin(), res.end(), sort_tin);
res.erase(unique(res.begin(), res.end()), res.end());

    So in the case you mentioned, res = {1, 2, 4, 5, 3, 6, 7} and my implementation still works right?

    → Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Consider a tree

1 2
2 3
2 4

And you try to build virtual tree on [1, 3, 4]. I think your algorithm will generate edges

1 3
2 4

However, we will expect

1 2
2 3
2 4
→ Reply
  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Check my comment above; in this case res already contains all 4 nodes.

    → Reply
    • »
      »
      »
      12 months ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it +10 Vote: I do not like it

      I think this means that your code differs a lot from normal implementation. Can you show the full implementation? It helps the discussion.

      → Reply
      • »
        »
        »
        »
        12 months ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        In case you don't want to provide the full implementation. I think the one described in the Chinese OI-Wiki may be related.

        → Reply
      • »
        »
        »
        »
        12 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Sorry, I should’ve specified better, but the code that I’m basing my implementation off of is the last USACO Guide link.

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, hide # ^ |
          ← Rev. 4  
          Vote: I like it 0 Vote: I do not like it

          Ah I see. Sorry I miss that link.

          I think then it's unnecessary to maintain a stack there. You can check the first implementation in the Chinese OI-Wiki (not the en one) as I shared above.

          The code looks like

          int dfn[MAXN];
int h[MAXN], m, a[MAXN], len;  // store key nodes

bool cmp(int x, int y) {
  return dfn[x] < dfn[y];  // sort by the dfs order
}

void build_virtual_tree() {
  sort(h + 1, h + m + 1, cmp);  // sort key nodes by the dfs order
  for (int i = 1; i < m; ++i) {
    a[++len] = h[i];
    a[++len] = lca(h[i], h[i + 1]);  // insert lca
  }
  a[++len] = h[m];
  sort(a + 1, a + len + 1, cmp);  // sort every nodes on the virtual tree by the dfs order
  len = unique(a + 1, a + len + 1) - a - 1;  // remove duplicated
  for (int i = 1, lc; i < len; ++i) {
    lc = lca(a[i], a[i + 1]);
    conn(lc, a[i + 1]);  // connect the edge
  }
}
          → Reply
          • »
            »
            »
            »
            »
            »
            12 months ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            Oh, I didn't even notice there were two implementations on OI Wiki! Is there any advantage of the second implementation over the first one then? It seems strictly more complicated with no noticeable advantage.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              For me, it's just that the one maintaining the stack is easier to understand and prove the correctness.

              → Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

If you are lazy to write O(1) LCA, maybe adding the extra constant factor factor to building virtual tree may not be good, idk. (Personally, I don't use O(1) lca often, it's not that much needed in every case.) Also, if the problem forces you to use O(N) memory, you need to use segment tree min queries for LCA, which will also give you log, thus by using the stack implementation you may save some constant factor. But obviosuly this is not very relevant...

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

This approach is correct, and OI-Wiki also introduces it as a naive approach before introducing the monostack approach.

The key is that you have to introduce either a much more complex algorithm like Four Russian to achieve a $$$O(n)\sim O(1)$$$ LCA, or an extra $$$\log$$$. By using a monostack you can build the virtual tree in $$$\Theta(n)$$$ without much coding.

→ Reply
  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    But the common implementation still call LCA every time a new node needs to be pushed into the stack.

    → Reply
    • »
      »
      »
      12 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Yes, this is my concern as well, as you can see lca is being called on line 10 of the second implementation. Wouldn't this lead to the same complexity? -firefly-

      → Reply
»
12 months ago, hide # |
 
Vote: I like it -19 Vote: I do not like it

As the author of the USACO.guide article and a big fan of shsh, I'm honored that he optimized my code, and everyone can blame my stupidity for the inefficiency and confusion caused here.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shsh (previous revision, new revision, compare).

→ Reply