What's the point of maintaining stack in virtual tree?

Revision en5, by shsh, 2025-04-21 21:33:44

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.

Tags virtual tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English shsh 2025-04-21 21:33:44 6 Tiny change: 'n OI Wiki (https://o' -> 'n OI Wiki [here](https://o'
en4 English shsh 2025-04-21 21:33:06 441
en3 English shsh 2025-04-20 21:25:36 39 Tiny change: '}\n~~~~~\n\nWe cou' -> '}\n~~~~~\n(From the USACO Guide implementation)\n\nWe cou'
en2 English shsh 2025-04-20 20:40:01 15 Tiny change: 'try/140066), there s' -> 'try/140066 , for instance), there s'
en1 English shsh 2025-04-20 20:36:58 955 Initial revision (published)