考虑这个把一个节点编号设为 \(\max\) 的操作在干什么。我们把当前编号最大的点 \(u\) 设为根，如果将 \(v\) 设为编号最大的点，那么容易发现当只有当整棵树只剩下 \((u,v)\) 这条链的时候才会开始从点 \(u\) 一个一个删到 \(v\)。而除了这条链上的点的相对位置是不会改变的。那每一次修改其实就是将一个点到根的链从原来的删除序列中拿出来放到最后，然后将新的点设为根。
可以发现，这个美妙的操作和 LCT 十分类似。于是我们可以用 LCT 维护这棵树的形态，每次将一个点到根变为实链的时候将这条链上的点赋一个新的颜色，这样在删除序列中一定是先按颜色排序，相同颜色的按当前的深度由大到小排序。使用树状数组维护颜色大小的前缀和，这题就做完了。复杂度 \(O(n\log ^2 n)\)。