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

Revision en2, by shsh, 2025-04-20 20:40:01

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]);
}

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.

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)