离线+树上主席树，主席树维护时间标记
注意查询时如果c<0要把c赋为0；
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#define re(i,l,r) for(int i=(l);i<=(r);i++)
#define rre(i,r,l) for(int i=(r);i>=(l);i--)
using namespace std;
template <typename Q>
void inin(Q &ret)
{
ret=;int f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=;ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
ret=f?-ret:ret;
}
const int xxx=;
int n,fa[xxx],w[xxx],head[xxx<<],next[xxx<<],zhi[xxx<<],ed;
void add(int a,int b)
{
next[++ed]=head[a],head[a]=ed,zhi[ed]=b;
next[++ed]=head[b],head[b]=ed,zhi[ed]=a;
}
namespace pou
{
int top[xxx],shen[xxx],son[xxx];
int dfs(int x)
{
int ret=,temp,Max=;
for(int i=head[x];i;i=next[i])if(zhi[i]!=fa[x])
{
shen[zhi[i]]=shen[x]+,fa[zhi[i]]=x;
temp=dfs(zhi[i]);ret+=temp;
if(Max<temp)Max=temp,son[x]=zhi[i];
}
return ret;
}
void dfs(int x,int t)
{
if(!x)return ;
top[x]=t;
dfs(son[x],t);
for(int i=head[x];i;i=next[i])if(zhi[i]!=fa[x]&&zhi[i]!=son[x])
dfs(zhi[i],zhi[i]);
}
int lca(int x,int y)
{
while(top[x]!=top[y])
if(shen[top[x]]>shen[top[y]])x=fa[top[x]];
else y=fa[top[y]];
return shen[x]<shen[y]?x:y;
}
}
namespace pst
{
int root[xxx],sum[xxx<<],ed,ch[xxx<<][];
void update(int l,int r,int L,int &R,int x)
{
R=++ed;sum[R]=sum[L]+(x?:);
if(!x){ch[R][]=ch[L][],ch[R][]=ch[L][];return ;}
if(l==r)return ;
int mid=(l+r)>>;
if(x<=mid)ch[R][]=ch[L][],update(l,mid,ch[L][],ch[R][],x);
else ch[R][]=ch[L][],update(mid+,r,ch[L][],ch[R][],x);
}
void build(int x)
{
update(,n,root[fa[x]],root[x],w[x]);
for(int i=head[x];i;i=next[i])if(zhi[i]!=fa[x])
build(zhi[i]);
}
int query(int l,int r,int x,int c)
{
if(c==)return ;
if(l>=&&r<=c)return sum[x];
int mid=(l+r)>>;
if(c<=mid)return query(l,mid,ch[x][],c);
else return query(l,mid,ch[x][],c)+query(mid+,r,ch[x][],c);
}
}
struct que
{
int x,y,c;
}sta[];int top;
int main()
{
inin(n);
re(i,,n)
{
int x;inin(x);
if(x)add(i,x);
}pou::shen[]=;
pou::dfs();
pou::dfs(,);
int q;inin(q);
re(i,,q)
{
int opt,x,y,c;inin(opt),inin(x);
if(opt==)inin(y),inin(c),sta[++top]=(que){x,y,i-c-};
else w[x]=w[x]?w[x]:i;
}
pst::build();
re(i,,top)
{
using namespace pou;
using namespace pst;
int temp=lca(sta[i].x,sta[i].y),x=sta[i].x,y=sta[i].y,c=sta[i].c;if(c<)c=;
printf("%d ",shen[sta[i].x]+shen[sta[i].y]-(shen[temp]<<)+);
printf("%d\n",query(,n,root[x],c)+query(,n,root[y],c)-*query(,n,root[fa[temp]],c)-(w[temp]<=c&&w[temp]>));
}
return ;
}