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.↵
↵
Edit: the usaco.guide module has since been updated, but I'm still not sure what advantage the second implementation on OI Wiki [here](https://oi-wiki.org/graph/virtual-tree/#%E7%AC%AC%E4%B8%80%E7%A7%8D%E6%9E%84%E9%80%A0%E8%BF%87%E7%A8%8B%E4%BA%8C%E6%AC%A1%E6%8E%92%E5%BA%8F--lca-%E8%BF%9E%E8%BE%B9) 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.
↵
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](https://oi-wiki.org/graph/virtual-tree/#%E7%AC%AC%E4%B8%80%E7%A7%8D%E6%9E%84%E9%80%A0%E8%BF%87%E7%A8%8B%E4%BA%8C%E6%AC%A1%E6%8E%92%E5%BA%8F--lca-%E8%BF%9E%E8%BE%B9) 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.
