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.



