[这里也可以看哦](https://foreverlasting1202.github.io/2019/10/01/YNOI2012D2T2/)
一道不难想而且代码较短的$YNOI$题。所以为什么都没人写写$YNOI$了啊，感觉$YNOI2012$冷清清的。
<!--more-->
拿过来一看，这个操作$1$感觉就很麻烦。子树先看成$dfs$序。模$x$等于$y$，这种操作好像也没有什么数据结构可以维护（可能是我孤陋寡闻了？），于是考虑暴力。
有一种显然的暴力就是直接对时间轴分块，然后询问的时候就遍历$O(B)$个修改，看看是否影响当前询问点。每$B$个修改就暴力更新一下，即对于每个修改每次一直跳$x$的深度，然后更新一下这些点。
这样跳有很多不好的地方，比如同一深度如果点很多就会越跳越多。于是我们稍微优化一下，按$dfs$序遍历每个询问，然后只维护模$x$等于$y$的深度上的权值，这样复杂度就是$O(n+B\ast \frac{n}{x})$，稍微注意一下不在一棵子树就要去掉之前贡献的细节。这样总复杂度就是（$n,m$同阶）$O(\frac{n}{B}(n+B\ast \frac{n}{x})+nB)$，即$O(\frac{n^2}{B}+\frac{n^2}{x}+nB)$。但这个$x$毕竟是$[1,n]$的，复杂度就会退化到$O(n^2)$了。
注意到当$x$比较小的时候，我们对$dfs$序分块有奇效。我们在每个块里维护一个二维数组$sum[x][y]$，表示当前块内模$x$等于$y$的点要加$sum[x][y]$的权值。显然这个当$x$比较小的时候能开的下。于是设个阈值$lim$，当$x\leq lim$的时候维护$dfs$序分块，否则继续对时间轴分块。这样时间复杂度就是$O(\frac{n^2}{B}+\frac{n^2}{lim}+nB+n\sqrt{n})$，在$B$取$\sqrt{n}$,$lim$取$\sqrt{n}$时最优，做到$O(n\sqrt{n})$，只不过此时空间复杂度是$O(n\ast lim)$，所以且行且珍惜。
其实删去其他子树贡献这个细节挺难写的。。。
code:
```cpp
//2019.10.1 by ljz
//email
[email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define lowbit(x) (x&-x)
#define gc getchar
#define kcz 1000000007
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline char gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
res s=0,ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//char sr[1<<21],z[20];
//int C=-1,Z=0;
//inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
//inline void print(res x){
// if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
// while(z[++Z]=x%10+48,x/=10);
// while(sr[++C]=z[Z],--Z);sr[++C]='\n';
//}
//inline int read() {
// res s=0,ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
inline LL Read() {
RG LL s=0;
res ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline LL Read() {
// RG LL s=0;
// res ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
//inline void write(RG unl x){
// if(x>10)write(x/10);
// putchar(int(x%10)+'0');
//}
//inline void swap(res &x,res &y) {
// x^=y^=x^=y;
//}
inline void add(res &x,const res &y){
x+=y,x>=kcz?x-=kcz:(x<0?x+=kcz:1);
}
inline int Add(const res &x,const res &y){
return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
}
inline int mul(const res &x,const res &y){
return int(1LL*x*y%kcz);
}
inline int sqr(const res &x){
return mul(x,x);
}
inline int mul(const res &x,const res &y,const res &d){
return int(1LL*x*y/d%kcz);
}
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=mul(ret,x);
x=mul(x,x),y>>=1;
}
return ret;
}
inline LL Qpow(RG LL x,res y){
RG LL ret=1;
while(y){
if(y&1)ret*=x;
x*=x,y>>=1;
}
return ret;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
// if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=3e5+10;
const int B=600;
const int C=300;
namespace MAIN{
int n,m;
vector<int> G[N];
int dfn[N],low[N],idx,dep[N],pos[N],mxdep;
void dfs(res x,res depx){
mxdep=max(mxdep,dep[pos[dfn[x]=++idx]=x]=depx);
for(auto tox:G[x])dfs(tox,depx+1);
low[x]=idx;
}
int lim;
int val[N],sum[B][C+10][C+10];
int pr[B],pl[B];
struct Que{
int a,l,r,x,y,z;
Que() {}
Que(res a,res l,res r,res x,res y,res z):a(a),l(l),r(r),x(x),y(y),z(z) {}
}que[B];
int quex;
vector<Que> E[N],F[N];
inline void MAIN(){
n=read(),m=read(),lim=int(sqrt(n));
for(res i=2;i<=n;i++)G[read()].pb(i);
dfs(1,0);
for(res i=1;i<=n;i++)pr[i/lim]=i;
for(res i=n;i;i--)pl[i/lim]=i;
while(m--){
res opt=read();
if(opt==1){
res a=read(),x=read(),y=read(),z=read(),l=dfn[a],r=low[a];
if(x<=C){
res L=l/lim,R=r/lim;
if(L==R){
for(res i=l;i<=r;i++)if((dep[pos[i]]-dep[a])%x==y)val[i]+=z;
}
else {
for(res i=l;i<=pr[L];i++)if((dep[pos[i]]-dep[a])%x==y)val[i]+=z;
for(res i=pl[R];i<=r;i++)if((dep[pos[i]]-dep[a])%x==y)val[i]+=z;
for(res i=L+1;i<R;i++)sum[i][x][(dep[a]+y)%x]+=z;
}
}
else {
que[++quex]=Que(a,l,r,x,y,z);
if(quex==lim){
for(res i=1;i<=n;i++)E[i].clear(),F[i].clear();
for(res i=1;i<=quex;i++)E[que[i].l].pb(que[i]),F[que[i].r+1].pb(que[i]);
static int dept[N];
for(res i=0;i<=mxdep;i++)dept[i]=0;
for(res i=1;i<=n;i++){
for(auto w:E[i]){
res now=dep[w.a]+w.y;
while(now<=mxdep)dept[now]+=w.z,now+=w.x;
}
for(auto w:F[i]){
res now=dep[w.a]+w.y;
while(now<=mxdep)dept[now]-=w.z,now+=w.x;
}
val[i]+=dept[dep[pos[i]]];
}
quex=0;
}
}
}
else {
res a=read(),id=dfn[a],I=id/lim,ans=val[id];
for(res x=1;x<=C;x++)ans+=sum[I][x][dep[a]%x];
for(res i=1;i<=quex;i++)if(que[i].l<=id&&id<=que[i].r&&(dep[a]-dep[que[i].a])%que[i].x==que[i].y)ans+=que[i].z;
printf("%d\n",ans);
}
}
}
}
int main() {
// srand(19260817);
// freopen("path.in","r",stdin);
// freopen("path.out","w",stdout);
MAIN::MAIN();
// Ot();
return 0;
}
```