#include<bits/stdc++.h> #define gc getchar using namespace std; const int N=2e5+10; int mx[N],mn[N];bool isb[N]; struct tree{ int ls,rs,fa,vl; }T[N]; int n,q; void pu(int x){ mx[x]=T[x].vl;mn[x]=T[x].vl; mx[x]=max(mx[x],max(mx[T[x].ls],mx[T[x].rs])); mn[x]=min(mn[x],min(mn[T[x].ls],mn[T[x].rs])); }int cnt=0,tot=0; void dete(int x){ if(isb[x]) cnt--;isb[x]=0; if(mx[T[x].ls]<=T[x].vl&&T[x].vl<=mn[T[x].rs]&&isb[T[x].ls]&&isb[T[x].rs]) cnt++,isb[x]=1; }int dfn[N],val[N],lp[N],rp[N],fa[N][22]; void dfs(int x){ if(!x) return ; fa[x][0]=T[x].fa; for(int i=1;i<=18;i++){ fa[x][i]=fa[fa[x][i-1]][i-1]; //cout<<x<<' '<<i<<' '<<fa[x][i]<<endl; } lp[x]=tot+1; dfs(T[x].ls); dfn[x]=++tot; dfs(T[x].rs); rp[x]=tot; pu(x);dete(x); }struct BIT{ int T[N]; #define lb(x) (x&(-x)) void upd(int x,int v){ for(int i=x;i<=n;i+=lb(i)) T[i]+=v; }int qry(int x){ int res=0; for(int i=x;i>0;i-=lb(i)) res+=T[i]; return res; } #undef lb }bit; bool chk(int x){ if(x==0) return 0; if(bit.qry(rp[x]-1)-bit.qry(lp[x]-1)>0) return 0; else return 1; }void upd(int x,int op){ int res=0; if(!chk(x)) return ; res++; for(int i=18;i>=0;i--){ if(chk(fa[x][i])){ x=fa[x][i];res+=1<<i; } }if(op==0) cnt-=res;else cnt+=res; }inline int read(){ int t=0,f=1;char ch=gc(); while(!(ch>='0'&&ch<='9')){ if(ch=='-') f=-1;ch=gc(); }while(ch>='0'&&ch<='9') t=t*10+ch-'0',ch=gc(); return t*f; } int main(){ n=read(),q=read(); for(int i=1;i<=n;i++){ int l=read(),r=read(); T[i].ls=l;T[i].rs=r; if(l!=0) T[l].fa=i; if(r!=0) T[r].fa=i; }for(int i=1;i<=n;i++) T[i].vl=read(); mn[0]=0x3f3f3f3f,mx[0]=0;isb[0]=1; dfs(1); for(int i=1;i<=n;i++) val[dfn[i]]=T[i].vl; for(int i=1;i<n;i++) if(val[i]>val[i+1]) bit.upd(i,1); while(q--){ int x=read(),v=read(); T[x].vl=v;upd(x,0); //for(int i=1;i<=n;i++) cout<<val[i]<<' ';cout<<endl; //for(int i=1;i<n;i++) cout<<(bit.qry(i)-bit.qry(i-1))<<' ';cout<<endl; //cout<<cnt<<endl; val[dfn[x]]=v; if(dfn[x]>1){ if(bit.qry(dfn[x]-1)-bit.qry(dfn[x]-2)>0){ bit.upd(dfn[x]-1,-1); }if(val[dfn[x]-1]>val[dfn[x]]) bit.upd(dfn[x]-1,1); }if(dfn[x]+1<n){ if(bit.qry(dfn[x])-bit.qry(dfn[x]-1)>0){ bit.upd(dfn[x],-1); }if(val[dfn[x]]>val[dfn[x]+1]) bit.upd(dfn[x],1); } int now=x;upd(x,1); //for(int i=1;i<=n;i++) cout<<isb[i]<<' '; printf("%d\n",cnt); } return 0; }