洛谷P3203_動態(tài)樹(Link Cut Tree)
2022-07-15 10:44 作者:Clayton_Zhou | 我要投稿
// https://www.luogu.com.cn/problem/P3203
程序采用編號1~n,和題目有所不同。
若x+k≤n,則連一條邊(x,x+k)。x的父節(jié)點為x+k
若x+k>n,則不連邊。x的父節(jié)點為0, 表示綿羊被彈飛。
那么題目中的修改操作就對應著樹的刪邊和加邊,所以要使用動態(tài)樹這個數(shù)據(jù)結構。
查詢操作即為從x到其最高祖先的路徑上點的個數(shù)。
本程序是最簡單的LCT,只使用了rotate, splay, access 這些基本操作。
標簽: