考虑这是一个\(LCT\)模板题。
感觉得多做一些题来熟悉\(LCT\)的操作。
这个题考虑对每个点向他往后跳的终点,如果会出界就不连边。
然后考虑\(LCT\)维护,也就是查询该点到原树根的距离。
那就\(access\),\(splay\),然后查询\(x\)的子树大小就行了。
断边的话,因为保证了树结构而且断的边都是子节点向父节点断的边,所以考虑\(access\),\(splay\)完,则\(x\)成为树根,那么他的父节点必为他的左儿子,直接双向断就行了。
[HNOI2010]弹飞绵羊
#include<iostream>
#include<cstdio>
#define ll long long
#define N 200009
ll f[N],c[N][2],s[N];//父亲,儿子,权值
#define l(x) c[x][0]
#define r(x) c[x][1]
#define f(x) f[x]
inline bool nroot(int x){return l(f(x)) == x || r(f(x)) == x;}//一个点是否不是splay的根
inline void up(int x){s[x] = s[l(x)] + s[r(x)] + 1;}
inline void rotate(int x){
// std::cout<<x<<std::endl;
int y = f(x),z = f(y),k = (r(y) == x),w = c[x][!k];
if(nroot(y))
c[z][r(z) == y] = x;c[x][!k] = y;c[y][k] = w;
if(w)f(w) = y;f(y) = x;f(x) = z;
up(y);up(x);
}
inline void splay(int x){
// std::cout<<x<<std::endl;
int y,z;
while(nroot(x)){
y = f(x);z = f(y);
if(nroot(y))
rotate((l(y) == x) ^ (l(z) == y)?x:y);
rotate(x);
}
up(x);
}
inline void access(int x){
for(int y = 0;x;x = f[y = x])
splay(x),c[x][1] = y,up(x);
}
ll n,m;
int main(){
scanf("%lld",&n);
for(int i = 1;i <= n;++i){
s[i] = 1;
ll k;
scanf("%lld",&k);
if(i + k <= n)
f[i] = i + k;
}
scanf("%lld",&m);
while(m -- ){
ll opt,x,y;
scanf("%lld",&opt);
if(opt & 1){
scanf("%lld",&x);
++x;
access(x),splay(x);
std::cout<<s[x]<<std::endl;
}else{
scanf("%lld%lld",&x,&y);
++x;
access(x),splay(x);
l(x) = f(l(x)) = 0;
if(x + y <= n)
f(x) = x + y;
up(x);
}
}
}