题目大意

把 $a$ 子树中所有与 $a$ 的距离模 $x$ 等于 $y$ 的节点权值加 $z$，并支持单点查询。

思路

根据经验，容易得到对于子树操作可以使用 dfs 序将一个子树转化为一个区间。假设节点 $i$ 的时间戳为 $dfn_i$ 且以 $i$ 为根的子树的大小为 $size_i$，那么如果点 $k$ 满足 $dfn_k\in[dfn_a,dfn_a+size_a]$ 那么易得 $k$ 为 $a$ 的子树内一点。

在把 $a$ 子树中所有与 $a$ 的距离模 $x$ 等于 $y$ 的节点满足他们的距离之差为 $y$ 的倍数。也就是说如果 $k$ 会被修改，那么它必然满足 $dfn_k\in[dfn_a,dfn_a+size_a]$ 且 $(dep_a-dep_k)\operatorname{mod}x=y$。

对于 $x>\sqrt{n}$ 的情况

因为在区间 $[dfn_a,dfn_a+size_a]$ 内需要修改的点并连续不方便维护，考虑将为何一个数组 $f_{i,j}$ 表示 $dfn$ 值为 $i$ 的节点，如果深度为 $j$ 那么增加的值为 $f_{i,j}$，也就是第 $i$ 个节点增加的值为 $f_{dfn_i,dep_i}$。对于所有满足 $dfn_o\in[dfn_a,dfn_a+size_a]$ 且 $(dep_a-p)\operatorname{mod} x=y$，将 $f_{dfn_o,p}$ 全部加 $z$。

对于 $p$ 我们可以直接暴力跳，因为 $x> \sqrt{n}$ 那么即使整棵树是一个链即深度为 $n$ 需要访问的点也不超过 $\sqrt{n}$ 个，时间复杂度可以接受。对于查询，找到深度的时间为 $O(1)$ 。

所以可以使用分块的思想在每一块进行差分，这个时间复杂度在修改的时候是 $O(1)$ 的而查询是 $O(\sqrt{n})$ 所以对于 $x> \sqrt{n}$ 的情况无论是修改还是查询的时间复杂度都是 $O(\sqrt{n})$ 的，可以接受。

对于 $x\le \sqrt{n}$ 的情况

考虑继续使用上面的方法求解，发现暴力跳的时间复杂度 $O(\dfrac{n}{x})$ 可能会退化成为 $O(n)$ 的不可以接受，所以考虑新的方法。

我们可以将 $mdf_{x,(dep_a+y)\operatorname{mod} x}$ 中 $[dfn_a,dfn_a+size_a]$ 全部加上 $z$，找到 $mdf_{x,(dep_a+y)\operatorname{mod} x}$ 的时间复杂度为 $O(1)$。

对于查询操作可以枚举模数 $x$，节点 $a$ 的答案就是 $\sum_{i=1}^{\lfloor \sqrt{n}\rfloor} mdf_{i,dep_a\operatorname{mod} i,dfn_a}$，找到 $i$ 和 $dep_a$ 时间复杂度的 $O(\sqrt{n})$。这个式子很好理解，之所以值枚举到 $\sqrt{n}$ 是因为所有第一维的修改都只是 $x$ 而只有 $x\le \sqrt{n}$ 的时候才会有修改，所以自然只需要遍历到 $\sqrt{n}$ 就可以找到所有数了。

我们可以使用分块进行维护，因为分块修改时时间复杂度是 $O(\sqrt{n})$ 而在单点查询时时间复杂度为 $O(1)$，对于 $x\le \sqrt{n}$ 的情况不论修改还是查询的时间复杂度均为 $O(\sqrt{n})$ 可以接受。

综上所述

我们可以单独处理不满一块的部分，使用上述方法处理整块，每一个的时间复杂度均为 $O(\sqrt{n})$，总共时间复杂度为 $O(m\sqrt{n})$ 可以接受。

在最后：注意空间！注意空间！注意空间！！！

AC Code

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
const int N=3e5+5,M=180,LEN=2000 ;
int n,f[N],dfn[N],siz[N],dep[N],cnt,mp[N],m,l[N],r[N],pos[N],q;
long long val[N],diff[M][N],mdf[M][305][305];
// mp[dfn[i]]=i 
vector<int> v[N];
void dfs(int x,int fa){
    siz[x]=1; 
	dep[x]=dep[fa]+1;
    dfn[x]=++cnt;
	mp[cnt]=x;
    for(int i:v[x]){
        if(i!=fa){
            dfs(i,x);
            siz[x]+=siz[i];
        }
    }
}
void pre(){
    m=n/LEN;
    for(int i=1;i<=m;i++){
        l[i]=(i-1)*LEN+1;
        r[i]=i*LEN;
    }
    if(r[m]<n){
        m++;
        l[m]=r[m-1]+1;
        r[m]=n;
    }
    for(int i=1;i<=m;i++){
        for(int j=l[i];j<=r[i];j++){
            pos[j]=i;
        }
    }
}
void update(int l,int r,int a,int b,int w){
    for (int i=l;i<=r;i++){
        if (dep[mp[i]]%a==b){
            val[i]+=w;
        }
    }
}
void change(int u,int a,int b,int w){
    int x=dfn[u],y=dfn[u]+siz[u]-1;
    int xx=pos[x],yy=pos[y];
    int now=(dep[u]+b)%a;
    if (xx==yy){ //散块 
        update(x,y,a,now,w);
        return;
    }
    update(x,r[xx],a,now,w);
    update(l[yy],y,a,now,w);
    if(a>300){ //第一种情况
        for(int i=dep[u]+b;i<=n;i+=a){
            diff[xx+1][i]+=w;
            diff[yy][i]-=w;
        }
    }
    else{ //第二种情况 
        for(int i=xx+1;i<yy;i++){
            mdf[i][a][now]+=w;
        }
    }
}
long long ask(int u){
    long long ans=val[dfn[u]];
    for (int i=1;i<=pos[dfn[u]];i++){
        ans+=diff[i][dep[u]];
    }
    for (int i=1;i<=300;i++){
        ans+=mdf[pos[dfn[u]]][i][dep[u]%i];
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        cin>>f[i];
        v[f[i]].push_back(i);
    }
    dfs(1,0);
    pre();
    for(int i=1,op,a,x,y,z;i<=q;i++){
        cin>>op>>a;
        if(op==1){
            cin>>x>>y>>z;
            change(a,x,y,z);;
        }
        else{
            cout<<ask(a)<<'\n';
        }
    }
    return 0;
}