树链剖分获取树上坐标的方法

作者： 作者的头像   Dessa ,  2024-08-07 20:06:10 ,  所有人可见 ,  阅读 4

0


在原来的代码上，在dfs2中将uw[idx]=a[u]改成uw[idx]=u,idd数组保存的是新id，nw数组一开始的作用是保存初始值，然后在线段树中build，但是在后面的操作中，nw数组里的值不会改变，只有tree的值会改变，所以我们可以开一个新数组保存原坐标，如果我们在线段树上有修改值有他们的新id（dfs序）获取线段树上某一点的值ans，如果这个值是这个点的新id，nw[ans]就是他的坐标

0 评论