题解区关了,但是我还是想说一下。
这道题可以不用二分而做到单 log 。
首先我们将 (x,y,z)→(y,2y−x,z) 称为右移,另一个称为左移。
那么对于每个关键状态,即左移若干次到不能再左移(右移同理)的状态,记录是由右移还是左移到达的。
答案的 LCA 一定是重合的关键点而儿子。
找到深度最深的关键点,如果同时是左移/右移到达的,答案一定是总深度减去两倍2关键点深度再减去两倍到达关键点的儿子中深度较浅一个中到关键点的距离。
如果一个左移,另一个右移,那么一定是总深度减去两倍2关键点深度。
直接 map 的时间复杂度是logN loglogN,简单哈希可以做到logN。
https://www.luogu.com.cn/record/50339620