(以下时间复杂度均把 \(n,q\) 视为同阶)

先考虑如果没有 \(3,4\) 操作怎么做。

对于 \(2\) 操作，在序列上我们直接枚举它的所有因子然后用分块维护，在树上注意到对于一个点加 \(k\) ，实际上是把它子树的所有点到根的距离加上了 \(k\) ，所以我们还需要实现一个在 dfn 序上区间加的分块，如果直接区间加的话这里复杂度就退化为 \(O(n)\) 了，但是我们只有单点查询，所以我们直接差分一下即可，这里直接用分块维护 dfn 序，时间复杂度 \(O(\sqrt n)\) 。查询的时候这部分操作在序列 \([l,r]\) 上的贡献就是分块 \([l,r]\) 的和，在树上的贡献就是对 dfn 分块的 \([1,dfn[u]]\) 的和。

对于 \(1\) 操作，如果 \(v > \sqrt n\) 那么我们直接暴力加即可，和 \(2\) 操作相同，然后如果 \(v \le \sqrt n\) 我们可以直接打标记，维护一下每个 \(v\) 一共加了多少，这里需要预处理一个数组 \(c[u][i]\) 表示 \(u\) 到根节点的路径上有多少节点编号是 \(i\) 的倍数。预处理时间复杂度是 \(O(n\sqrt n)\) 的，修改是 \(O(\sqrt n)\) 的。在 \(6\) 操作的时候，直接枚举 \(v\) 然后求一个 \(\sum\limits_{v=1}^{\sqrt n}c[u][v] \times tag[v]\) 即可。时间复杂度 \(O(\sqrt n)\) ，在 \(5\) 操作的时候直接对于这 \(\sqrt n\) 个 \(v\) 计算一下在 \([l,r]\) 内有多少个数是它的倍数即可，时间复杂度 \(O(\sqrt n)\) 。

所以 \(1,2\) 操作的总时间复杂度是 \(O(n\sqrt n)\) 的。

那我们接下来就不需要管 \(1,2\) 操作了，因为不同操作的贡献是独立的，开始考虑 \(3\) 操作，在序列上我们直接用线段树维护即可。在链上的操作我们考虑用分块的操作，对于散块，我们直接暴力修改即可（和 \(2\) 操作相同） 对于整块，我们直接打一个 tag 即可，这里我们需要预处理一个数组 \(c2[u][id]\) 表示 \(u\) 到 \(1\) 节点的路径上有多少节点的编号在序列上是属于 \(id\) 这个块的。在 \(5\) 操作的时候，直接线段树即可，在 \(6\) 操作的时候，枚举每一个块然后计算 \(c2[u][i]\times tag2[i]\) 即可。单次操作时间复杂度 \(O(\sqrt n)\) ，总时间复杂度 \(O(n\sqrt n)\) 。

对于 \(4\) 操作，我们用树剖维护链上的贡献，对于链对序列产生的贡献，我们还是考虑分块维护，容易发现我们可以将链加转化为到根节点的加法，然后我们维护一个序列 \(a\)， \(a_i\) 表示这个在 dfn 序中位置一共加了多少，用分块维护它的前缀和。在 \(6\) 操作的时候，直接树剖即可。在 \(5\) 操作的时候，对于整块就直接用类似于 \(3\) 操作的方式维护，对于散块就利用我们处理的 \(a\) 数组的前缀和，这个点加上的值是等于它子树内所有节点操作的值，所以直接求一段 dfn 序上的前缀和即可。单次操作时间复杂度 \(O(\sqrt n)\) ， 总时间复杂度 \(O(n\sqrt n)\) 。

所以总时间复杂度为 \(O(n\sqrt n)\) 。

bool M1;
#include <bits/stdc++.h>
using namespace std;
#define XY cerr<<"XY"<<endl
#define MKF cerr<<"MKF"<<endl
#define CONNECT_BASE(x,y) x##y
#define CONNECT(x,y) CONNECT_BASE(x,y)
#define DEBUG_BASE(x) cerr<<#x<<'='<<x<<" "
#define DEB_1(x) DEBUG_BASE(x)
#define DEB_2(x,y) DEB_1(x),DEB_1(y)
#define DEB_3(x,y,z) DEB_1(x),DEB_2(y,z)
#define DEB_4(a,b,c,d) DEB_1(a),DEB_3(b,c,d)
#define DEB_5(a,b,c,d,e) DEB_1(a),DEB_4(b,c,d,e)
#define DEB_6(a,b,c,d,e,f) DEB_1(a),DEB_5(b,c,d,e,f)
#define COUNT_BASE(_1,_2,_3,_4,_5,_6,x,...) x
#define COUNT(...) COUNT_BASE(__VA_ARGS__,6,5,4,3,2,1,0)
#define D(...) cerr<<"[In Line "<<__LINE__<<"]: ",CONNECT(DEB_,COUNT(__VA_ARGS__))(__VA_ARGS__),cerr<<endl
#define NAME(x) #x
#define INNAME(x) NAME(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define look_time cerr<<(double)clock()/CLOCKS_PER_SEC<<'\n'
#define look_memory cerr<<abs(&M1-&M2)/1024.0/1024.0<<'\n'
// #define int long long                                       //use it if possible
#define F(i,a,b) for(int i=(a),i##end=(b);i<=(i##end);++i)
#define UF(i,a,b) for(int i=(a),i##end=(b);i>=(i##end);--i)
#define pb(x) push_back(x)
#define gc() getchar()
#define ret return 
#define pc putchar
#define popcount(x) __builtin_popcount(x)
using ll=long long;
using lll=__int128;
using PII=pair<int,int>;
using uint=unsigned;
using db=double;
using DB=long double;
mt19937 rng(time(NULL));
inline void init();
inline void IO();

const int maxn=2e5+5;
const int base=450;


ll tag[base+10];int n;
int cnt[maxn][base+5];
int vis[maxn],cnt2[maxn][base+5];

struct Tree
{
    int h[maxn],e[maxn<<1],ne[maxn<<1],idx;
    int rk[maxn],siz[maxn],son[maxn],f[maxn];
    int top[maxn],dfn[maxn],tim,dep[maxn];
    struct rnode
    {
        int l,r;ll sum,tag;
    }tre[maxn<<2];
    void push_up(int k)
    {
        tre[k].sum=tre[k<<1].sum+tre[k<<1|1].sum;
    }
    void push_down(int k)
    {
        tre[k<<1].sum+=(tre[k<<1].r-tre[k<<1].l+1)*tre[k].tag;
        tre[k<<1|1].sum+=(tre[k<<1|1].r-tre[k<<1|1].l+1)*tre[k].tag;
        tre[k<<1].tag+=tre[k].tag;
        tre[k<<1|1].tag+=tre[k].tag;
        tre[k].tag=0;
    }
    void add(int u,int v)
    {
        e[idx]=v,ne[idx]=h[u],h[u]=idx++;
    }
    void dfs(int u,int fa)
    {
        siz[u]=1;f[u]=fa;
        for(int i=h[u];~i;i=ne[i])
        {
            int v=e[i];
            if(v==fa) continue;
            dfs(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]]) son[u]=v;
        }
    }
    void dfs2(int u,int fa,int topf)
    {
        dfn[++tim]=u;
        rk[u]=tim;
        top[u]=topf;dep[u]=dep[fa]+1;
        if(son[u]) dfs2(son[u],u,topf);
        for(int i=h[u];~i;i=ne[i])
        {
            int v=e[i];
            if(v==fa) continue;
            if(v==son[u]) continue;
            dfs2(v,u,v);
        }
    }
    int LCA(int u,int v)
    {
        while(top[u]!=top[v])
        {
            if(dep[top[u]]<dep[top[v]]) swap(u,v);
            u=f[top[u]];
        }
        if(dep[u]<dep[v]) return u;
        return v;
    }
    void build(int k,int l,int r)
    {
        tre[k].l=l,tre[k].r=r;
        if(l==r) return ;
        int mid=l+r>>1;
        build(k<<1,l,mid);
        build(k<<1|1,mid+1,r);
        push_up(k);
    }
    void update(int k,int l,int r,ll x)
    {
        if(tre[k].l>=l&&tre[k].r<=r)
        {
            tre[k].sum+=1ll*(tre[k].r-tre[k].l+1)*x;
            tre[k].tag+=x;
            return ;
        }
        push_down(k);
        int mid=tre[k].l+tre[k].r>>1;
        if(l<=mid) update(k<<1,l,r,x);
        if(r>mid) update(k<<1|1,l,r,x);
        push_up(k);
    }
    ll query(int k,int l,int r)
    {
        if(tre[k].l>=l&&tre[k].r<=r) return tre[k].sum;
        push_down(k);
        int mid=tre[k].l+tre[k].r>>1;ll ans=0;
        if(l<=mid) ans+=query(k<<1,l,r);
        if(r>mid) ans+=query(k<<1|1,l,r);
        return ans;
    }
    void update_l(int u,int v,ll x)
    {
        while(top[u]!=top[v])
        {
            if(dep[top[u]]<dep[top[v]]) swap(u,v);
            update(1,rk[top[u]],rk[u],x);
            u=f[top[u]];
        }
        update(1,min(rk[u],rk[v]),max(rk[u],rk[v]),x);
    }
    ll query_l(int u)
    {
        ll ans=0;
        while(top[u]!=1)
        {
            ans+=query(1,rk[top[u]],rk[u]);
            u=f[top[u]];
        }
        ans+=query(1,1,rk[u]);
        return ans;
    }
}Tre1,seg;

struct BLOCK
{
    ll tag[maxn/base+5],a[maxn];
    inline int ID(int x) {return (x-1)/base+1;}
    inline int L(int x) {return (x-1)*base+1;}
    inline int R(int x) {return min(n,x*base);}
    void add(int x,ll k)
    {
        if(x>n) return ;
        a[x]+=k;
        tag[ID(x)]+=k;
    }
    ll query(int l,int r)
    {
        ll ans=0;
        if(ID(l)==ID(r))
        {
            for(int i=l;i<=r;i++) ans+=a[i];
            return ans;
        }
        for(int i=l;i<=R(ID(l));i++) ans+=a[i];
        for(int i=L(ID(r));i<=r;i++) ans+=a[i];
        for(int i=ID(l)+1;i<=ID(r)-1;i++) ans+=tag[i];
        return ans;
    }
}seq,tre;




void Init(int u,int fa)
{
    F(i,1,base) cnt[u][i]+=cnt[Tre1.f[u]][i],cnt2[u][i]=cnt2[Tre1.f[u]][i];
    cnt2[u][(u-1)/base+1]++;
    for(int i=Tre1.h[u];~i;i=Tre1.ne[i])
    {
        int v=Tre1.e[i];
        if(v==fa) continue;
        Init(v,u);
    }
}

ll calc_seq(int l,int r)
{
    ll ans=0;
    for(int i=1;i<=base;i++) ans+=((r/i)-((l-1)/i))*tag[i];
    return ans;
}

ll calc_tre(int u)
{
    ll ans=0;
    for(int i=1;i<=base;i++) ans+=tag[i]*cnt[u][i];
    return ans;
}

struct I2L
{
    ll tag[base+5];
    inline int ID(int x) {return (x-1)/base+1;}
    inline int L(int x) {return (x-1)*base+1;}
    inline int R(int x) {return min(n,x*base);}
    void add(int x,ll k)
    {
        tre.add(Tre1.rk[x],k);
        tre.add(Tre1.rk[x]+Tre1.siz[x],-k);
    }
    void add(int l,int r,ll x)
    {
        if(ID(l)==ID(r))
        {
            F(i,l,r) add(i,x);
            ret;
        }
        F(i,l,R(ID(l))) add(i,x);
        F(i,L(ID(r)),r) add(i,x);
        F(i,ID(l)+1,ID(r)-1) tag[i]+=x;
    }
    ll query(int u)
    {
        ll ans=0;
        F(i,1,ID(n)) ans+=tag[i]*cnt2[u][i];
        return ans;
    }
}TREE;

struct L2I
{
    ll tag[base+5],a[maxn],tag2[base+5];
    inline int ID(int x) {return (x-1)/base+1;}
    inline int L(int x) {return (x-1)*base+1;}
    inline int R(int x) {return min(n,x*base);}
    void add(int l,int r,ll x)
    {
        if(ID(l)==ID(r))
        {
            F(i,l,r) a[i]+=x;
            ret;
        }
        F(i,l,R(ID(l))) a[i]+=x;
        F(i,L(ID(r)),r) a[i]+=x;
        F(i,ID(l)+1,ID(r)-1) tag2[i]+=x;
    }
    void add(int u,ll x)
    {
        for(int i=1;i<=base;i++) tag[i]+=cnt2[u][i]*x;
        add(Tre1.rk[u],n,x);
    }
    inline ll get_val(int x)
    {
        if(x==0) return 0;
        return tag2[ID(x)]+a[x];
    }
    ll query(int x)
    {
        return get_val(Tre1.rk[x]+Tre1.siz[x]-1)-get_val(Tre1.rk[x]-1);
    }
    inline ll query(int l,int r)
    {
        ll ans=0;
        if(ID(l)==ID(r))
        {
            F(i,l,r) ans+=query(i);
            ret ans;
        }
        F(i,l,R(ID(l))) ans+=query(i);
        F(i,L(ID(r)),r) ans+=query(i);
        F(i,ID(l)+1,ID(r)-1)ans+=tag[i];
        return ans;
    }
}SEQ;

bool M2;

inline void mian()
{
    int q,flag=0;
    cin>>n>>q;
    memset(Tre1.h,-1,sizeof(Tre1.h));
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        Tre1.add(i,x);
        Tre1.add(x,i);
    }
    for(int i=1;i<=base;i++)
        for(int j=i;j<=n;j+=i)
            cnt[j][i]++;
    Tre1.dfs(1,0);
    Tre1.dfs2(1,0,1);
    seg.build(1,1,n);
    Tre1.build(1,1,n);
    Init(1,0);
    while(q--)
    {
        int opt;
        cin>>opt;
        if(opt==1)
        {
            int v,x;
            cin>>v>>x;
            if(v<=base) tag[v]+=x;
            else
            {
                for(int i=v;i<=n;i+=v)
                {
                    seq.add(i,x);
                    tre.add(Tre1.rk[i],x);
                    tre.add(Tre1.rk[i]+Tre1.siz[i],-x);
                }
            }
        }
        else if(opt==2)
        {
            int v,x;
            cin>>v>>x;
            for(int i=1;i*i<=v;i++)
            {
                if((v%i)==0)
                {
                    seq.add(i,x);
                    tre.add(Tre1.rk[i],x);
                    tre.add(Tre1.rk[i]+Tre1.siz[i],-x);
                    if(i*i!=v)
                    {
                        seq.add(v/i,x);
                        tre.add(Tre1.rk[v/i],x);
                        tre.add(Tre1.rk[v/i]+Tre1.siz[v/i],-x);
                    }
                }
            }
        }
        else if(opt==3)
        {
            int l,r,x;
            cin>>l>>r>>x;
            seg.update(1,l,r,x);
            TREE.add(l,r,x);
        }
        else if(opt==4)
        {
            int u,v,x;cin>>u>>v>>x;
            int lca=Tre1.LCA(u,v);
            Tre1.update_l(u,v,x);
            SEQ.add(u,x);
            SEQ.add(v,x);
            SEQ.add(lca,-x);
            if(Tre1.f[lca]) SEQ.add(Tre1.f[lca],-x);
        }
        else if(opt==5)
        {
            int r;
            cin>>r;flag++;
            ll ans=seq.query(1,r)+calc_seq(1,r)+seg.query(1,1,r)+SEQ.query(1,r);
            cout<<ans<<"\n";
        }
        else
        {
            int u;
            cin>>u;flag++;
            ll ans=tre.query(1,Tre1.rk[u])+calc_tre(u)+TREE.query(u)+Tre1.query_l(u);
            cout<<ans<<"\n";
        }
    }
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    int T=1;
     IO();              
    // #define multitest 1
#ifdef multitest
    cin>>T;
#endif
    while(T--) init(),mian();
    look_time;
    look_memory;
    return 0;
}

inline void init()
{
    
}

#define FILEIO tree
inline void IO()
{
#ifdef FILEIO
    freopen(INNAME(FILEIO)".in","r",stdin),freopen(INNAME(FILEIO)".out","w",stdout);
#endif
}

/*
g++ D.cpp -o D -std=c++14 -O2 -Wall -Wextra -fno-ms-extensions -fsanitize=address,undefined&&./D

10 2
1 2 3 4 5 1 6 4 9 
4 2 9 10
6 3

122:6 807

*/