题目大意：给你一棵树，有两种操作，一个是修改某个点的权值，另一个是询问两点之间的距离以及路径上小于某个值的数的个数。
询问两点之间距离直接lca即可，对于求个数的问题可以用主席树完成。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=;char ch=getchar();
for(;ch<''||ch>'';ch=getchar());
for(;ch>=''&&ch<='';ch=getchar())s=s*+ch-'';
return s;
}
int N,Q;
struct node{
int opt,x,y,c,t;
}q[];
int to[],next[],tot,h[];
int root[],ls[],rs[],size[];
int c[],rt,cnt;
int fa[][],dep[];
void add(int x,int y){
tot++;to[tot]=y;next[tot]=h[x];h[x]=tot;
}
void insert(int l,int r,int Ort,int Nrt,int x){
if(l==r){size[Nrt]=size[Ort]+;return;}
int mid=(l+r)>>;
if(x<=mid){
ls[Nrt]=++cnt;
rs[Nrt]=rs[Ort];
insert(l,mid,ls[Ort],ls[Nrt],x);
}else{
rs[Nrt]=++cnt;
ls[Nrt]=ls[Ort];
insert(mid+,r,rs[Ort],rs[Nrt],x);
}
size[Nrt]=size[ls[Nrt]]+size[rs[Nrt]];
}
void dfs(int x){
for(int i=;i<=;++i)
if(dep[x]<(<<i))break;
else fa[x][i]=fa[fa[x][i-]][i-];
for(int i=h[x];i;i=next[i]){
int v=to[i];
if(dep[v])continue;
dep[v]=dep[x]+;
fa[v][]=x;
if(c[v])insert(,Q,root[x],root[v]=++cnt,c[v]);
else root[v]=root[x];
dfs(v);
}
}
void init(){
N=read();
for(int i=;i<=N;++i){
int x=read();
if(x==)rt=i;
else add(x,i);
}
Q=read();
for(int i=;i<=Q;++i){
q[i].opt=read();
if(q[i].opt==)q[i].x=read(),q[i].y=read(),q[i].c=read();
else{
q[i].t=read();
if(!c[q[i].t])c[q[i].t]=i;
}
}
dep[rt]=;
if(c[rt])insert(,Q,root[],root[rt]=++cnt,c[rt]);
dfs(rt);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int d=dep[x]-dep[y];
for(int i=;i<=;++i)
if(d&(<<i))
x=fa[x][i];
if(x==y)return x;
for(int i=;i>=;--i)
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if(x==y)return x;
return fa[x][];
}
int ask(int l,int r,int rrt,int lrt,int x){
if(x<=)return ;
if(l==r)return size[rrt]-size[lrt];
int mid=(l+r)>>;
if(x<=mid)return ask(l,mid,ls[rrt],ls[lrt],x);
else return size[ls[rrt]]-size[ls[lrt]]+ask(mid+,r,rs[rrt],rs[lrt],x);
}
void work(){
for(int i=;i<=Q;++i){
if(q[i].opt==){
int k=lca(q[i].x,q[i].y);
int k1=dep[q[i].x]+dep[q[i].y]-*dep[k]+;
int k2=ask(,Q,root[q[i].x],root[fa[k][]],i-q[i].c-)+ask(,Q,root[q[i].y],root[k],i-q[i].c-);
printf("%d %d\n",k1,k2);
}
}
}
int main(){
init();
work();
return ;
}