标签 LCT 下的文章

一道傻逼 LCT ,结果调了好久。

首先直接离线处理,发现询问在中间做和在最后做是一样的,相当于一棵一棵树扫过去用 LCT 动态维护一个区间换父亲的操作,考虑用 LCT 建虚点,搞一搞即可。

需要注意这题查询两点间的距离的时候不能直接 split 出来,因为 LCT 上的 LCA 有可能是虚点,从而忽略了虚 LCA 到实 LCA 中间一段距离对答案的贡献。同时还注意点小细节,比如 1 号点的范围 233 .

另外这题保证了操作合法,就没必要费力不讨好的每次都 get_root 一下了,否则可能会 TLE 飞 。。。

关于如何求 LCT 上的 LCA :对于 \operatorname{access} 操作保存下最后一次的 \operatorname{splay}y 。先 \operatorname{makeroot}(root) ,再 \operatorname{access}(u) ,最后 \operatorname{access}(v) 返回的值就是答案。

READ MORE