洛谷P3203_动态树(Link Cut Tree)

// https://www.luogu.com.cn/problem/P3203

程序采用编号1∼n，和题目有所不同。

若x+k≤n，则连一条边(x,x+k)。x的父节点为x+k

若x+k>n，则不连边。x的父节点为0， 表示绵羊被弹飞。

那么题目中的修改操作就对应着树的删边和加边，所以要使用动态树这个数据结构。

查询操作即为从x到其最高祖先的路径上点的个数。

本程序是最简单的LCT，只使用了rotate, splay, access 这些基本操作。