思路：
可持久化树状数组模板；
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 200005
#define maxm maxn*100
int deep[maxn],f[maxn],id[maxn],top[maxn],cnt,soot;
int head[maxn],V[maxn],E[maxn],lar[maxn],size[maxn];
int val[maxm],root[maxn],ch[maxm][],tot,Tl,Tr,n,m,Ans;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'')Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void build(int &now,int l,int r)
{
now=++tot;
if(l==r) return;int mid=l+r>>;
build(ch[now][],l,mid);
build(ch[now][],mid+,r);
}
void add(int &now,int pre,int l,int r,int to,int x)
{
now=++tot,val[now]=val[pre]+x;
if(l==r) return;int mid=l+r>>;
if(to<=mid) add(ch[now][],ch[pre][],l,mid,to,x),ch[now][]=ch[pre][];
else add(ch[now][],ch[pre][],mid+,r,to,x),ch[now][]=ch[pre][];
}
int lowbit(int x)
{
return x&(-x);
}
void add(int to1,int to2,int x)
{
while(to1<=n) add(root[to1],root[to1],,m,to2,x),to1+=lowbit(to1);
}
void dfs1(int now)
{
deep[now]=deep[f[now]]+,size[now]=;
for(int i=head[now];i;i=E[i])
{
dfs1(V[i]),size[now]+=size[V[i]];
if(size[lar[now]]<size[V[i]]) lar[now]=V[i];
}
}
void dfs2(int now,int chain)
{
top[now]=chain,id[now]=++cnt;
root[id[now]]=root[];
if(lar[now])
{
dfs2(lar[now],chain);
for(int i=head[now];i;i=E[i])
{
if(V[i]==lar[now]) continue;
dfs2(V[i],V[i]);
}
}
}
int query(int now,int l,int r)
{
if(l>=Tl&&r<=Tr) return val[now];
int mid=l+r>>,res=;
if(Tl<=mid) res+=query(ch[now][],l,mid);
if(Tr>mid) res+=query(ch[now][],mid+,r);
return res;
}
int query(int l,int r)
{
l--;int res=;
while(r) res+=query(root[r],,m),r-=lowbit(r);
while(l) res-=query(root[l],,m),l-=lowbit(l);
return res;
}
int query(int x,int y,int tl,int tr)
{
int res=;Tl=tl,Tr=tr;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) res+=query(id[top[y]],id[y]),y=f[top[y]];
else res+=query(id[top[x]],id[x]),x=f[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
res+=query(id[x],id[y]);
return res;
}
int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(deep[top[x]]>deep[top[y]]) x=f[top[x]];
else y=f[top[y]];
}
return deep[x]<deep[y]?deep[x]:deep[y];
}
int main()
{
freopen("data.txt","r",stdin);
freopen("data.out","w",stdout);
in(n);int op,u,v,c;
for(int i=;i<=n;i++)
{
in(f[i]);
if(!f[i]) soot=i;
else E[i]=head[f[i]],V[i]=i,head[f[i]]=i;
}
in(m);
build(root[],,m),dfs1(soot),dfs2(soot,soot);
for(int i=;i<=m;i++)
{
in(op);
if(op==)in(u),add(id[u],i,);
else
{
in(u),in(v),in(c),Ans=deep[u]+deep[v]-*lca(u,v)+;
printf("%d ",Ans);
if(i-c->=) printf("%d\n",query(u,v,,i-c-));
else printf("0\n");
}
}
return ;
}