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

Правка en4, от shsh, 2025-04-21 21:33:06

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 (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.

Теги virtual tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский shsh 2025-04-21 21:33:44 6 Tiny change: 'n OI Wiki (https://o' -> 'n OI Wiki [here](https://o'
en4 Английский shsh 2025-04-21 21:33:06 441
en3 Английский 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 Английский shsh 2025-04-20 20:40:01 15 Tiny change: 'try/140066), there s' -> 'try/140066 , for instance), there s'
en1 Английский shsh 2025-04-20 20:36:58 955 Initial revision (published)