图片加载可能有点慢，请跳过题面先看题解，谢谢

这个题好多解法啊。。。

可以主席树，可以按深度将操作排序离线做

我这里是动态开点线段树，对每一个深度种一棵线段树，下标是节点的\(dfs\)序

然后这个做法就很简单啊。。。

$

$

//made by Hero_of_Someone#include
    
     #include
     
      #include
      
       #define inf (1<<30)#define N (600010)#define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();  if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int n,m,deep[N],w[N],st[N],ed[N],tim;int rt[N],sum[N<<2],ls[N<<2],rs[N<<2],cnt;int num,head[N],nxt[N<<1],to[N<<1];il void add(int u,int v){   nxt[++num]=head[u];to[num]=v;head[u]=num;   nxt[++num]=head[v];to[num]=u;head[v]=num;}il void dfs(int x,int f){   st[x]=++tim;   deep[x]=deep[f]+1;   for(int i=head[x];i;i=nxt[i]){      int v=to[i]; if(v==f) continue;      dfs(v,x);   }   ed[x]=tim;}il void update(int &x,int l,int r,int k,int val){   if(!x) x=++cnt;   if(l==r){ sum[x]=val; return ; }   RG int mid=(l+r)>>1;   if(k<=mid) update(ls[x],l,mid,k,val);   else update(rs[x],mid+1,r,k,val);   sum[x]=sum[ls[x]]+sum[rs[x]];}il void init(){   n=gi();   for(int i=1;i<=n;i++) w[i]=gi();   for(int i=1;i
       
        >1,ret=0;   if(R<=mid) return query(ls[x],l,mid,L,R);   else if(L>mid) ret+=query(rs[x],mid+1,r,L,R);   else return query(ls[x],l,mid,L,mid)+query(rs[x],mid+1,r,mid+1,R);}il void work(){   m=gi();   while(m--){      int op=gi(),u=gi(),v=gi();      if(op==1) update(rt[deep[u]],1,n,st[u],v);      else{          if(deep[u]+v>n){ puts("0"); continue; }         printf("%d\n",query(rt[deep[u]+v],1,n,st[u],ed[u]));      }   }}int main(){ init(); work(); return 0; }