情报网络中共有n名情报员。每名情报员口J-能有若T名（可能没有）下线，除1名大头日外其余n-1名情报员有且仅有1名上线。奈特公司纪律森严，每名情报员只能与自己的上、下线联系，同时，情报网络中仟意两名情报员一定能够通过情报网络传递情报。
奈特公司每天会派发以下两种任务中的一个任务：
1．搜集情报：指派T号情报员搜集情报
2．传递情报：将一条情报从X号情报员传递给Y号情报员
情报员最初处于潜伏阶段，他们是相对安全的，我们认为此时所有情报员的危险值为0；-旦某个情报员开始搜集情报，他的危险值就会持续增加，每天增加1点危险值（开始搜集情报的当天危险值仍为0，第2天危险值为1，第3天危险值为2，以此类推）。传递情报并不会使情报员的危险值增加。
为了保证传递情报的过程相对安全，每条情报都有一个风险控制值C。余特公司认为，参与传递这条情报的所有情报员中，危险值大于C的情报员将对该条情报构成威胁。现在，奈特公司希望知道，对于每个传递情报任务，参与传递的情报员有多少个，其中对该条情报构成威胁的情报员有多少个。n,q<=2*10^5
离线统计每个人第一次搜集情报的时间戳，之后主席树维护每个点到根路径上关于时间戳的权值线段树即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
#define N 201000
int n,m,root,tot;
int head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
struct node
{
int x,y,c;
}a[N];
int fa[N][20],Log[N],dep[N],val[N];
struct seg
{
int ls,rs,siz;
}t[N*20];
int rt[N],se;
void insert(int &r1,int r2,int l,int r,int x)
{
r1=++se; t[r1].siz=t[r2].siz+1;
if(l==r) return ; int mid=(l+r)>>1;
if(x<=mid) t[r1].rs=t[r2].rs,insert(t[r1].ls,t[r2].ls,l,mid,x);
else t[r1].ls=t[r2].ls,insert(t[r1].rs,t[r2].rs,mid+1,r,x);
}
int query(int p,int l,int r,int x)
{
if(!p) return 0;
if(x>=r) return t[p].siz;
int mid=(l+r)>>1;
if(x<=mid) return query(t[p].ls,l,mid,x);
else return t[t[p].ls].siz+query(t[p].rs,mid+1,r,x);
}
void dfs(int x)
{
insert(rt[x],rt[fa[x][0]],1,m+1,val[x]);
for(int i=1;i<=Log[dep[x]];++i) fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=nxt[i])
{
dep[to[i]]=dep[x]+1;
fa[to[i]][0]=x;
dfs(to[i]);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
int i,t=dep[x]-dep[y];
for(i=0;i<=Log[t];++i) if((t>>i)&1) x=fa[x][i];
if(x==y) return x;
for(i=Log[dep[x]];~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
scanf("%d",&n);
int i,x;
for(i=1;i<=n;++i)
{
scanf("%d",&x);
if(x) add(x,i);
else root=i;
}
scanf("%d",&m); int op;
for(i=1;i<=n;++i) val[i]=m+1;
for(i=1;i<=m;++i)
{
scanf("%d",&op);
if(op==1) ++tot,scanf("%d%d%d",&a[tot].x,&a[tot].y,&a[tot].c)
,a[tot].c=i-a[tot].c-1;
else
{
scanf("%d",&x);
val[x]=min(val[x],i);
}
}
for(i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
dfs(root);
for(i=1;i<=tot;++i)
{
x=lca(a[i].x,a[i].y);
printf("%d %d\n",dep[a[i].x]+dep[a[i].y]-(dep[x]<<1)+1
,query(rt[a[i].x],1,m+1,a[i].c)+query(rt[a[i].y],1,m+1,a[i].c)
-(query(rt[x],1,m+1,a[i].c)<<1)+(val[x]<=a[i].c));
}
return 0;
}