#include<iostream>
using namespace std;
int n,m,stack[1000005],top,k[1000005];
struct node
{
	int son[2],fa,ans,tag;
}tree[1000005];
bool isroot(int now){return (tree[tree[now].fa].son[0]!=now && tree[tree[now].fa].son[1]!=now);}
void push_down(int now)
{
	if(tree[now].tag)
	{
		tree[now].tag=0;
		tree[tree[now].son[0]].tag^=1,tree[tree[now].son[1]].tag^=1;
		swap(tree[now].son[0],tree[now].son[1]);
	}
}
void push_up(int now){tree[now].ans=tree[tree[now].son[0]].ans+tree[tree[now].son[1]].ans+1;}
void ronate(int now)
{
	int fir=tree[now].fa,sec=tree[fir].fa,c=(tree[fir].son[0]==now);
	if(!isroot(fir))
		tree[sec].son[tree[sec].son[1]==fir]=now;
	tree[fir].son[!c]=tree[now].son[c],tree[tree[now].son[c]].fa=fir;
	tree[now].son[c]=fir,tree[fir].fa=now;
	tree[now].fa=sec;
	push_up(fir),push_up(now);
}
void splay(int now)
{
	int tmp=now;
	stack[top=1]=now;
	while(!isroot(tmp))
		stack[++top]=tree[tmp].fa,tmp=tree[tmp].fa;
	while(top)
		push_down(stack[top--]);
	while(!isroot(now))
	{
		int fir=tree[now].fa,sec=tree[fir].fa;
		if(!isroot(fir))
			(tree[fir].son[0]==now)^(tree[sec].son[0]==fir)?ronate(now):ronate(fir);
		ronate(now);
	}
}
void access(int now)
{
	for(int i=0;now;i=now,now=tree[now].fa)
		splay(now),tree[now].son[1]=i,push_up(now);
}
void makeroot(int now){access(now),splay(now),tree[now].tag^=1;}
int findroot(int now)
{
	access(now),splay(now);
	while(tree[now].son[0])
		now=tree[now].son[0];
	return now;
}
void link(int x,int y)
{
	if(y>n)	return;
	if(findroot(x)==findroot(y))	return;
	makeroot(x),tree[x].fa=y;
}
void split(int x,int y){makeroot(x),access(y),splay(y);}
void cut(int x,int y)
{
	if(y>n)	return;
	split(x,y);
	//if(tree[y].son[0]!=x || tree[x].son[1])
	//	return;
	tree[y].son[0]=tree[x].fa=0,push_up(y);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	tree[i].ans=1;
	for(int i=1;i<=n;i++)
	{
		cin>>k[i];
		if(k[i]+i<=n)
			tree[i].fa=k[i]+i;
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int op,u,v,w;
		cin>>op;
		if(op==1)
		{
			cin>>u,++u;access(u),splay(u);
			cout<<tree[u].ans<<endl;
		}
		else
		{
			cin>>u>>v,++u;
			cut(u,u+k[u]);
			k[u]=v;
			link(u,u+k[u]);
		}
	}
	return 0;
}

这是原来的代码，一直是全WA。

#include<iostream>
using namespace std;
int n,m,stack[1000005],top,k[1000005];
struct node
{
	int son[2],fa,ans,tag;
}tree[1000005];
bool isroot(int now){return (tree[tree[now].fa].son[0]!=now && tree[tree[now].fa].son[1]!=now);}
void push_down(int now)
{
	if(tree[now].tag)
	{
		tree[now].tag=0;
		tree[tree[now].son[0]].tag^=1,tree[tree[now].son[1]].tag^=1;
		swap(tree[now].son[0],tree[now].son[1]);
	}
}
void push_up(int now){tree[now].ans=tree[tree[now].son[0]].ans+tree[tree[now].son[1]].ans+1;}
void ronate(int now)
{
	int fir=tree[now].fa,sec=tree[fir].fa,c=(tree[fir].son[0]==now);
	if(!isroot(fir))
		tree[sec].son[tree[sec].son[1]==fir]=now;
	tree[fir].son[!c]=tree[now].son[c],tree[tree[now].son[c]].fa=fir;
	tree[now].son[c]=fir,tree[fir].fa=now;
	tree[now].fa=sec;
	push_up(fir),push_up(now);
}
void splay(int now)
{
	int tmp=now;
	stack[top=1]=now;
	while(!isroot(tmp))
		stack[++top]=tree[tmp].fa,tmp=tree[tmp].fa;
	while(top)
		push_down(stack[top--]);
	while(!isroot(now))
	{
		int fir=tree[now].fa,sec=tree[fir].fa;
		if(!isroot(fir))
			(tree[fir].son[0]==now)^(tree[sec].son[0]==fir)?ronate(now):ronate(fir);
		ronate(now);
	}
}
void access(int now)
{
	for(int i=0;now;i=now,now=tree[now].fa)
		splay(now),tree[now].son[1]=i,push_up(now);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	tree[i].ans=1;
	for(int i=1;i<=n;i++)
	{
		cin>>k[i];
		if(k[i]+i<=n)
			tree[i].fa=k[i]+i;
	}
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int op,u,v,w;
		cin>>op;
		if(op==1)
		{
			cin>>u,++u;access(u),splay(u);
			cout<<tree[u].ans<<endl;
		}
		else
		{
			cin>>u>>v,++u;
			access(u),splay(u);
			tree[tree[u].son[0]].fa=0,tree[u].son[0]=0;
			if(u+v<=n)
				tree[u].fa=u+v;
			push_up(u);
		}
	}
	return 0;
}

照着题解的思路改了一改，大致没变，却AC了。