2021“MINIEYE杯”中国大学生算法设计超级联赛（3）

A. Bookshop 对树进行轻重链剖分并求出DFS序，在DFS的过程中先DFS一个点的重儿子，再DFS它的轻儿子们，那么每条重链在DFS序上是连续的。对于a56爆大奖在线娱乐询问$(x,y,z)$，令$t$为$x$和$y$的LCA，那么从$x$出发走到$t$的过程在DFS序里对应从右往左的$O(\log n)$
posted @ 2022-01-14 21:08  Claris  阅读(179)  评论(0)  编辑  收藏  举报