思路：

注意到len<=10

按照权值max-min<=sqrt(n)*len 分块

记一下前缀和  每修改sqrt(n)次以后重新分块

 

修改的时候整块打标记  两边重构

（这题常数卡得要死   找同学要来fread才过）

 查询的时候 就 二分答案 O(sqrt(n))判断

二分的上界要实时根据maxdeep变化才能过

 

//By SiriusRen#include
     
      using namespace std;const int N=100050;int n,m,op,xx,yy,len,limval,Block,deep[N],cnt,dfn[N],lst[N],maxdep;int first[N],next[N],v[N],w[N],tot,a[N],pos[N],maxx[N],minn[N],L[N],R[N],tag[N];unsigned short sum[1200][33333];inline int nextChr() {    static const int siz=1<<22;    static char buf[siz],*chr=buf+siz;    if(chr==buf+siz)fread(chr=buf,1,siz,stdin);    return int(*chr++);}inline int read(){    register int r=0,c=nextChr();    for(;c<48;c=nextChr());    for(;c>47;c=nextChr())r=(r<<3)+(r<<1)+c-48;    return r;}inline void add(int x,int y,int z){w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;}void dfs(int x){    dfn[x]=++cnt,a[cnt]=deep[x];    for(int i=first[x];~i;i=next[i])        deep[v[i]]=deep[x]+w[i],dfs(v[i]);    lst[x]=cnt;}void rebuild(int x){    for(int i=0;i<=limval;i++)sum[x][i]=0;maxx[x]=0;    for(int i=L[x];i<=R[x];i++)sum[x][a[i]]++,maxx[x]=max(maxx[x],a[i]);    for(int i=1;i<=maxx[x];i++)sum[x][i]+=sum[x][i-1];}void build(){    int bs=0;limval=n*len/Block;maxdep=0;    for(int i=1;i<=n;i++)a[i]=a[i]+tag[pos[i]],maxdep=max(maxdep,a[i]);    for(int i=1;i<=n;){        bs++,L[bs]=R[bs]=i,maxx[bs]=minn[bs]=a[i];        while(i<=n&&max(maxx[bs],a[i])-min(minn[bs],a[i])<=limval&&R[bs]-L[bs]<=Block)            R[bs]=i,pos[i]=bs,maxx[bs]=max(maxx[bs],a[i]),minn[bs]=min(minn[bs],a[i]),i++;    }    for(int i=1;i<=bs;i++){        maxx[i]-=(tag[i]=minn[i]);        for(int j=L[i];j<=R[i];j++)a[j]-=tag[i];        rebuild(i);    }}void change(int l,int r,int wei){    if(pos[l]==pos[r]){
   for(int i=l;i<=r;i++)a[i]+=wei;rebuild(pos[l]);}    else{        for(int i=l;i<=R[pos[l]];i++)a[i]+=wei;rebuild(pos[l]);        for(int i=L[pos[r]];i<=r;i++)a[i]+=wei;rebuild(pos[r]);        for(int i=pos[l]+1;i<=pos[r]-1;i++)tag[i]+=wei;    }}int kth(int l,int r,int wei){    int ans=0;    if(pos[l]==pos[r]){
   for(int i=l;i<=r;i++)ans+=(tag[pos[l]]+a[i]<=wei);}    else{        for(int i=l;i<=R[pos[l]];i++)ans+=(tag[pos[l]]+a[i]<=wei);        for(int i=L[pos[r]];i<=r;i++)ans+=(tag[pos[r]]+a[i]<=wei);        for(int i=pos[l]+1;i<=pos[r]-1;i++)if(wei>=tag[i])            ans+=sum[i][min(maxx[i],wei-tag[i])];    }return ans;}int bsrch(int l,int r,int k){    if(r-l+1
      
       >1;        if(kth(l,r,mid-1)+1<=k)lft=mid+1,ans=mid;        else rit=mid-1;    }return ans;}int main(){    memset(first,-1,sizeof(first));    n=read(),m=read(),len=read(),Block=min(n,(int)sqrt(n));    for(int i=2;i<=n;i++)xx=read(),yy=read(),add(xx,i,yy);    dfs(1),build();    while(m--){        if(cnt>Block)cnt=0,build();        op=read(),xx=read(),yy=read();        if(op==1)printf("%d\n",bsrch(dfn[xx],lst[xx],yy));        else limval+=yy,maxdep+=yy,change(dfn[xx],lst[xx],yy),cnt++;    }}