传送门
对于每个点离线处理出向上走2i2^i2i班车到的最上面的点。
然后每个询问(u,v)(u,v)(u,v)先把(u,v)(u,v)(u,v)倍增到刚好走不到lcalcalca的情况(有一个点如果就是lcalcalca直接特判)
然后考虑最后把(u′,v′)(u',v')(u′,v′)连起来需要走一次还是两次。
这个就是一个二维数点问题了。
用dfsdfsdfs序求出每个点管辖的子树表示的区间。
然后对于询问(a,b)(a,b)(a,b)在dfs到aaa时统计bbb子树的答案。
把aaa子树的修改操作更新之后再统计一次bbb子树的答案。
如果两次答案一样说明某个端点在aaa子树中的班车对bbb子树均没有影响。
这样需要走2次，否则只用走1次。
代码