#include<bits/stdc++.h> using namespace std; int n,ls[200005],rs[200005],v[200005],fa[200005][18],q,k,x; bool isbst[200005]; int bstcnt=0; int dfn[200005],a[200005],bg[200005],ed[200005],tot; int sm[800005]; #define ls (p<<1) #define rs (p<<1|1) #define mid (l+r>>1) void pu(int p){ sm[p]=sm[ls]+sm[rs]; return; } void bd(int l,int r,int p){ if(l==r){ sm[p]=(a[l]>a[l+1]); return; } bd(l,mid,ls),bd(mid+1,r,rs); pu(p); } void upd(int l,int r,int id,int p){ if(l==r){ sm[p]=(a[l]>a[l+1]); return; } if(id<=mid)upd(l,mid,id,ls); else upd(mid+1,r,id,rs); pu(p); return; } int qu(int l,int r,int ml,int mr,int p){ if(ml<=l&&r<=mr)return sm[p]; int res=0; if(mid>=ml)res+=qu(l,mid,ml,mr,ls); if(mid<mr)res+=qu(mid+1,r,ml,mr,rs); return res; } void prt(int l,int r,int p){ if(l==r){ cout<<l<<" "<<r<<" "<<sm[p]<<endl; return; } prt(l,mid,ls),prt(mid+1,r,rs); } #undef ls #undef rs #undef mid void dfs(int p){ bg[p]=tot+1; if(ls[p]){dfs(ls[p]);} a[dfn[p]=++tot]=v[p]; if(rs[p]){dfs(rs[p]);} ed[p]=tot; return; } int mx[200005],mn[200005]; bool chk(int p){ return qu(1,n-1,bg[p],ed[p]-1,1)==0; } int calc(int p){ if(!chk(p))return 0; int res=1; for(int i=17;~i;i--){ if(fa[p][i]&&chk(fa[p][i]))p=fa[p][i],res+=(1<<i); } return res; } void dfs1(int p){ isbst[p]=1; mx[p]=mn[p]=v[p]; if(ls[p]){ dfs1(ls[p]); mx[p]=max(mx[p],mx[ls[p]]); mn[p]=min(mn[p],mn[ls[p]]); isbst[p]&=isbst[ls[p]]; isbst[p]&=(mx[ls[p]]<=v[p]); } if(rs[p]){ dfs1(rs[p]); mx[p]=max(mx[p],mx[rs[p]]); mn[p]=min(mn[p],mn[rs[p]]); isbst[p]&=isbst[rs[p]]; isbst[p]&=(mn[rs[p]]>=v[p]); } // cout<<p<<" "<<isbst[p]<<endl; bstcnt+=isbst[p]; return; } int main(){ //freopen("bst.in","r",stdin); //freopen("bst.out","w",stdout); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>ls[i]>>rs[i]; if(ls[i])fa[ls[i]][0]=i; if(rs[i])fa[rs[i]][0]=i; } for(int i=1;i<=17;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; for(int i=1;i<=n;i++)cin>>v[i]; dfs(1); // for(int i=1;i<=n;i++)cout<<dfn[i]<<" "; // cout<<endl<<endl; // for(int i=1;i<=n;i++)cout<<a[i]<<" "; // cout<<endl; bd(1,n-1,1); dfs1(1); // prt(1,n-1,1); while(q--){ cin>>k>>x; a[dfn[k]]=x; bstcnt-=calc(k); // cout<<k<<endl; // cout<<calc(k)<<" "; upd(1,n-1,dfn[k],1); upd(1,n-1,dfn[k]-1,1); bstcnt+=calc(k); // cout<<calc(k)<<endl; cout<<bstcnt<<endl; // for(int i=1;i<=n;i++)cout<<a[i]<<" "; // cout<<endl; // prt(1,n,1); } return 0; }