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.



