#include<bits/stdc++.h> #define ll long long #define mk make_pair #define fi first #define se second // #define int long long using namespace std; inline int read(){ int x=0,f=1;char c=getchar(); for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;} for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15); return x*f; } const int mod=998244353; int ksm(int x,ll y,int p=mod){ int ans=1;y%=(p-1); for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p; return ans%p; } int inv(int x,int p=mod){return ksm(x,p-2,p)%p;} mt19937 rnd(20070819); int randint(int l,int r){return rnd()%(r-l+1)+l;} void add(int &x,int v){x+=v;if(x>=mod)x-=mod;} void Mod(int &x){if(x>=mod)x-=mod;} int cmod(int x){if(x>=mod)x-=mod;return x;} template<typename T>void cmax(T &x,T v){x=max(x,v);} template<typename T>void cmin(T &x,T v){x=min(x,v);} const int N=2e6+5; vector<int>G[N]; int dep[N],idfn[N],fa[N],dfn[N],top[N],sz[N],hson[N],dfc=0; int n,q,Endp[N],sons[N],root[N]; ll a[N]; struct zkw{ int M,k;ll d[N<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) void build(){ M=1,k=0;while(M<n)M<<=1,k++; for(int i=1;i<=M*2-1;i++)d[i]=0; } void pushup(int p){d[p]=max(d[ls(p)],d[rs(p)]);} void mdf(int p,ll v){ p+=M-1;d[p]=v; for(int i=1;i<=k;i++)pushup(p>>i); } ll qmax(int l,int r){ ll res=0; for(l+=M-1,r+=M;l<r;l>>=1,r>>=1){ if(l&1)cmax(res,d[l++]); if(r&1)cmax(res,d[--r]); } return res; } #undef ls #undef rs }T; struct S{ ll mx,val;int siz; S(ll V=0,int Si=0):mx(V),siz(Si){} }; S e(){return S(0,0);} S d[N];int rk[N],ls[N],rs[N],tot=0; void clear(){d[0]=e();for(int i=1;i<=tot;i++)rk[i]=ls[i]=rs[i]=0;tot=0;} #define ls(p) (ls[p]) #define rs(p) (rs[p]) void pushup(int p){ d[p].siz=d[ls(p)].siz+d[rs(p)].siz+1; d[p].mx=max({d[ls(p)].mx,d[rs(p)].mx,d[p].val}); } int build(int c){ // cout<<"build c = "<<c<<endl; int p=++tot; if(tot>=1000000)cerr<<"tot = "<<tot<<endl; rk[p]=rnd(),ls[p]=rs[p]=0; d[p].mx=d[p].val=c,d[p].siz=1; return p; } int merge(int p,int q){ if(!p||!q)return p+q; if(rk[p]>rk[q]){rs[p]=merge(rs[p],q),pushup(p);return p;} else{ls[q]=merge(p,ls[q]),pushup(q);return q;} } void split(int p,int k,int &x,int &y){ if(!p){x=y=0;return ;} if(d[ls(p)].siz+1<=k)x=p,split(rs(p),k-d[ls(p)].siz-1,rs(x),y),pushup(p); else y=p,split(ls(p),k,x,ls(y)),pushup(p); } ll qmax(int &p,int l,int r){ if(l>r)return 0; // cout<<"qmax p = "<<p<<" l,r = "<<l<<" "<<r<<endl; int pa=0,pb=0,pc=0,pd=0; split(p,r,pa,pb),split(pa,l-1,pc,pd); ll ans=d[pd].mx; // cout<<"siz = "<<d[pc].siz<<" "<<d[pd].siz<<" "<<d[pb].siz<<" ans = "<<ans<<endl; p=merge(pc,merge(pd,pb)); return ans; } void addv(int &p,int x,ll v){ // cout<<"addv p = "<<p<<" x,v = "<<x<<" "<<v<<endl; int pa=0,pb=0,pc=0,pd=0; split(p,x,pa,pb),split(pa,x-1,pc,pd); d[pd].mx+=v,d[pd].val+=v,p=merge(pc,merge(pd,pb)); } #undef ls #undef rs void dfs1(int u){ sz[u]=1,dep[u]=dep[fa[u]]+1; for(int v:G[u]){ dfs1(v),sz[u]+=sz[v]; if(sz[v]>sz[hson[u]])hson[u]=v; } } void dfs2(int u,int tp){ idfn[dfn[u]=++dfc]=u,top[u]=tp; if(hson[u])dfs2(hson[u],tp); else{ ll v=0; // cout<<"Get heavy link : "; for(int i=dfn[tp];i<=dfn[u];i++){ cmax(v,a[idfn[i]]); root[tp]=merge(root[tp],build(a[idfn[i]])); // cout<<idfn[i]<<" "; } // cout<<"mx = "<<v<<" root = "<<root[tp]<<endl; // print(root[tp],0); Endp[tp]=u,T.mdf(dfn[tp],v); } for(int v:G[u])if(v!=hson[u])dfs2(v,v); } set<int>Leaf; vector<pair<int,ll> >mdfs; vector<int>mdf_l; void Shift(int x,int lim){ // cout<<"Shift Leaf = "<<x<<" lim = "<<lim<<endl; int t=top[x]; if(dep[t]>=dep[lim]){ int A=0,B=0; split(root[t],1,A,B); if(dep[t]>dep[lim])mdfs.emplace_back(mk(t,d[A].mx)); d[A].mx=d[A].val=0; root[t]=merge(B,A); // cout<<" -> siz "<<t<<" = "<<d[root[t]].siz<<endl; } else{ int A=0,B=0,C=0,D=0; split(root[t],dep[lim]-dep[t],A,B),split(B,1,C,D); d[C].mx=d[C].val=0; root[t]=merge(merge(A,D),C); // cout<<" -> siz "<<t<<" = "<<d[root[t]].siz<<endl; } mdf_l.emplace_back(x); } void Modify(int x){ // cout<<"Modify x = "<<x<<endl; int L=dfn[x],R=dfn[x]+sz[x]-1; auto itl=Leaf.lower_bound(L),itr=Leaf.upper_bound(R); for(auto it=itl;it!=itr;++it){ int y=idfn[*it]; Shift(y,x); } for(auto [p,w]:mdfs){ int q=fa[p]; // cout<<" p,w = "<<p<<" "<<w<<" q = "<<q<<endl; addv(root[top[q]],dep[q]-dep[top[q]]+1,w); // cout<<" -> mx "<<top[q]<<" = "<<d[root[top[q]]].mx<<endl; } for(int x:mdf_l){ // cout<<"x = "<<x<<" sons = "<<sons[x]<<endl; int t=top[x]; if(sons[x]==0){ Leaf.erase(Leaf.find(dfn[x])); Endp[t]=fa[x],sons[fa[x]]--; if(top[x]==top[fa[x]])Leaf.insert(dfn[fa[x]]); } ll v=qmax(root[t],1,dep[Endp[t]]-dep[t]+1); T.mdf(dfn[t],v); } mdfs.clear(),mdf_l.clear(); // cout<<"-> Leaves = ";for(int x:Leaf)cout<<idfn[x]<<" ";puts(""); } void Qry(int x){ // cout<<"Qry x = "<<x<<endl; int t=top[x],e=Endp[t]; ll ans=qmax(root[t],dep[x]-dep[t]+1,dep[e]-dep[t]+1); cmax(ans,T.qmax(dfn[x],dfn[x]+sz[x]-1)); cout<<ans<<'\n'; } signed main(void){ //freopen("eternal.in","r",stdin); //freopen("eternal.out","w",stdout); n=read(),q=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=2;i<=n;i++){ fa[i]=read(),sons[fa[i]]++; G[fa[i]].emplace_back(i); } T.build(),dfs1(1),dfs2(1,1); for(int i=1;i<=n;i++)if(sons[i]==0)Leaf.insert(dfn[i]); // Qry(1); for(int _=1;_<=q;_++){ int op=read(),x=read(); if(op==1)Qry(x); else Modify(x); } return 0; }