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](https://usaco.guide/plat/VT?lang=cpp) 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.
↵
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.
